【学习笔记】CF1672G Cross Xor

记$R_i$表示第$i$行元素异或和，$L_i$表示第$i$列元素异或和。那么矩阵全为零时显然$L_i,R_i$全为零。

如果$n$,$m$都是偶数，那么每次操作$(i,j)$相当于把$L_k(k\ne i)$ 和 $R_k(k\ne j)$ 翻转。我们可以看成只对$L_i,R_j$翻转，这又相当于只翻转$(i,j)$这一个点，因此任意$01$矩阵都是可以还原的。

如果$n$是奇数，$m$是偶数，那么操作$(i,j)$相当于把$L_k(k\ne i)$和所有$R_k$翻转，发现只和$i$有关，结论是$R_k$必须全为$0$或全为$1$。

求方案数则对于每个右部点钦定一条边即可。

如果$n,m$都是奇数，那么操作$(i,j)$相当于把所有$L_k$和$R_k$翻转，于是结论很明显，必须初始全为$0$或全为$1$。

至于计数部分，如果$(i,j)$是问号就在二分图上连一条边，对于一个连通块要对每条边定$0/1$边权使点权满足奇偶性。可以考虑构建生成树，对于不在生成树上的边可以随便定，对于在生成树上的边的边权是唯一确定的。

#include
#define fi first
#define se second
#define ll long long
#define pb push_back
#define db double
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int mod=998244353;
int n,m,K,W,num,vis[4005],in[4005],L[2005],R[2005];
int V,E;
char s[2005][2005];
vector<int>g[4005];
ll fpow(ll x,ll y){
	ll z(1);for(;y;y>>=1){
		if(y&1)z=z*x%mod;
		x=x*x%mod;
	}return z;
}
void dfs(int u){
	vis[u]=num,V++;
	W^=(u<=n)?L[u]:R[u-n];
	for(auto v:g[u]){
		if(!vis[v]){
			dfs(v);
		}if(u<=n&&vis[v]==num)E++;
	}
}
ll solve(int f){
	ll res=1;
	for(int i=1;i<=n+m;i++)vis[i]=0;
	for(int i=1;i<=n+m;i++){
		if(!vis[i]){
			num++,V=E=W=0,dfs(i);
			if(W!=f*V%2)return 0;
			res=res*fpow(2,E-V+1)%mod;
		}
	}return res;
}
ll solve1(int f){
	int c=0;
	for(int i=1;i<=m;i++){
		if(R[i]!=f&&!in[n+i]){
			return 0;
		}if(in[n+i])c++;
	}return fpow(2,K-c);
}
ll solve2(int f){
	int c=0;
	for(int i=1;i<=n;i++){
		if(L[i]!=f&&!in[i]){
			return 0;
		}if(in[i])c++;
	}
	return fpow(2,K-c);
}
int main(){
	cin>>n>>m;for(int i=1;i<=n;i++){
		scanf("%s",s[i]+1);
		for(int j=1;j<=m;j++){
			if(s[i][j]=='1')L[i]^=1,R[j]^=1;
			if(s[i][j]=='?')in[i]++,in[n+j]++,K++,g[i].pb(n+j),g[n+j].pb(i);
		}
	}
	if(n%2==0&&m%2==0){
		cout<<fpow(2,K);
	}
	else if(n%2==1&&m%2==0){
		cout<<(solve1(0)+solve1(1))%mod;
	}
	else if(n%2==0&&m%2==1){
		cout<<(solve2(0)+solve2(1))%mod;
	}
	else {
		cout<<(solve(0)+solve(1))%mod;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77