题意:

给你一个$n\times m$的棋盘(n,m<=1e6),每个方格里填入1或0,要求每个$2\times 2$的方格中1为奇数个.有一些格子已经填了1或0,求总方案数.

分析:

题意可以转化为:每$2\times 2$方格中的异或值为1.
假设我们在棋盘上选择了一些点,这些点的异或值为x.如果我们继续选择一个$2\times 2$的方格中的点,那么异或值将变为x^1.选择方格的时候,已经选过的再选一遍,对x的影响就消除了,因此相当于它没有被选,因此选与不选也成为了异或的过程.
因此我们可以选择一些恰当的方格,使得真正被选择的格子比较恰当.
比如,通过尝试,我们可以知道:
对于都是偶数的x,y,有:(1,1)^(x,y)^(1,y)^(x,1)=1
对于其他的x,y,有:(1,1)^(x,y)^(1,y)^(x,1)=0
这样,对于任何一个已知格子,我们都可以求出第一行和第一列的某些格子的相等或不相等的关系.这种关系可以利用带权并查集轻松维护.

但是还是有一个需要注意的地方:如何判定无解.

对于x,y都不是1的已知格子,我们用它维护并查集.
对于x,y中存在1的已知格子,我们用它来强制将一个并查集设为已知,或者判断是否与已经已知的并查集冲突,来判断无解.

至此该算法就可以在luogu和BZOJ上AC了.