【学习笔记】CF1054

是我降智了。

开始在想一些抽屉原理之类的东西，发现不太行。

注意到，一个位置上的$0,1$移到左上角或右下角最多需要两步，那么我们可以将初末状态都移成$0$全部在$(1,1)$上，$1$全部在$(n,n)$上，两部分都最多需要$2s$步，然后就做完了。

具体做法可以自己编，总之是有一点繁琐。

复制粘贴半天才发现我把串翻转过来就行了，我是joker

二分图，但是我没看出来。

事实上，只要第一步正确，剩下的就非常容易了：我们将初始局面看成，每一个交点处连接两条横竖线段。那么只要不产生多余的交点即可，两个交点有可能合并起来让答案减少$1$。将行列离散化过后相当于$n$个点的二分图，有 n 2 n^2 n2条边，求最大独立集，然后就做完了。

没想到可以直接在残留网络上找方案，妙啊

下次研究一下残留网络的性质

不会做，只会照搬题解。

令 S i S_i Si​表示包含点$i$的社区的集合。如果一个社区的大小为$1$，那么显然可以直接删去；否则考虑叶子节点$x$，设其父亲节点为$y$，那么一个连通块如果包含$x$，显然也会包含$y$，也就是 S x ⊆ S y S_x\\subseteq S_y Sx​⊆Sy​。这个限制看着非常亲切啊，因为假设我们知道了叶子节点$x$，那么把所有社区中的$x$删去，再将$x$向$y$连边就转化为一个子问题了。那么我们每次取出 ∣ S i ∣ |S_i| ∣Si​∣最小的作为$x$，然后再找到父节点$y$（其中 S x ⊆ S y S_x\\subseteq S_y Sx​⊆Sy​），然后重复上述操作就做完了。

复杂度 O ( n 2 m w ) O(\\frac{n^2m}{w}) O(wn2m​)。

调不出来

好像要用队列写，但不知道为啥。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
int T,n,m,vis[2005],sz[2005];
bitset<2005>b[2005];
string str;
vector<pair<int,int>>edges;void solve(){edges.clear();for(int i=1;i<n;i++){int x=-1,y=-1;for(int j=0;j<n;j++){if(!vis[j]&&(x==-1||b[j].count()<b[x].count())){x=j;}}vis[x]=1;for(int j=0;j<n;j++){if(!vis[j]&&(b[j]&b[x])==b[x]){y=j;break;}}if(y==-1){cout<<"NO"<<"\\n";return;}edges.pb({x,y});for(int j=b[x]._Find_first();j!=b[x].size();j=b[x]._Find_next(j)){if(--sz[j]==1){b[y][j]=0;}}}cout<<"YES"<<"\\n";for(auto x:edges){cout<<x.fi+1<<" "<<x.se+1<<"\\n";}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>T;while(T--){cin>>n>>m;for(int i=0;i<n;i++)b[i].reset(),vis[i]=0;for(int i=0;i<m;i++){cin>>str,sz[i]=0;for(int j=0;j<n;j++){if(str[j]=='1')sz[i]++;}if(sz[i]>1){for(int j=0;j<n;j++){if(str[j]=='1')b[j][i]=1;}}}solve();}
}

这是一道数学题。

因为$p$是质数，根据欧拉定理，记 c k = ∑ i 2 j 3 m o d 490018 = k a i b j c_k=\\sum_{i^2j^3\\bmod 490018=k}a_ib_j ck​=∑i2j3mod490018=k​ai​bj​，那么答案是 ∑ c k x k \\sum c_kx^k ∑ck​xk。

为什么这么拆，是因为前面很像一个卷积的形式。

根据中国剩余定理，我们只需要考虑模$2,491,499$的余数，其中$491,499$都是质数因此一定有原根，$491$有原根$2$，$499$有原根$7$。因此，我们取 i 2 i^2 i2, j 3 j^3 j3的离散对数（也就是原根的指数）就能把乘法转换成加法，而模$2$相当于是与运算。即求 c i , j , k = ∑ i 1 and  i 2 = 1 , j 1 + j 2 = j , k 1 + k 2 = k a i 1 , j 1 , k 1 b i 2 , j 2 , k 2 c_{i,j,k}=\\sum_{i_1\\text{and }i_2=1,j_1+j_2=j,k_1+k_2=k}a_{i_1,j_1,k_1}b_{i_2,j_2,k_2} ci,j,k​=∑i1​and i2​=1,j1​+j2​=j,k1​+k2​=k​ai1​,j1​,k1​​bi2​,j2​,k2​​。这里涉及到二维$fft$的问题，可以先按行做一遍卷积，再按列做一遍卷积，$idft$也同理。不过注意 i 2 , j 3 i^2,j^3 i2,j3是$491,499$倍数的时候 没有原根，这部分需要暴力处理。

这道题有点难写。代码先咕了。