题目：
http://www.lydsy.com/JudgeOnline/problem.php?id=2303
题解:
很神奇的思路，膜一发大佬http://www.cnblogs.com/HHshy/p/5840018.html#undefined
设S(i,j)=a[i][j]^a[i+1][j]^a[i][j+1]^a[i+1][j+1]。那么将S（1,1）^S(1,2)^…^S(1,j)^S(2,1)^…^S(2,j)^…..^S(i,j)展开，对于i相同的一行（如S（1,1）^S(1,2)^…^S(1,j)），我们可以先然看出其结果为开头的a[i][1]^a[i][j]，同时其在下一层的异或结果也是a[i+1][1]^a[i+1][j]，那么再把每一行合并，最终我们得到此式的化简：a[1][1]^a[i+1][1]^a[1][j+1]^a[i+1][j+1]，然后当i，j均为奇数时，我们得知a[1][1]^a[i+1][1]^a[1][j+1]^a[i+1][j+1]==1，否则为0，再把那个+1缩掉，即：（(i|j)&1）==0时，a[1][1]^a[i][1]^a[1][j]^a[i][j]==1，否则为0.设a[1][1]^a[i][1]^a[1][j]^a[i][j]为z,再移一下项，我们得到z^a[1][1]^a[i][j]==a[i][1]^a[1][j]，然后枚举a[1][1]的值，再用并查集把有关的a[i][1]与a[1][j]连接起来，判断是否会出现矛盾，如果没有矛盾，我们就得到了一部分答案。最后把两个a[1][1]值的贡献加和即可。
#include<cstdio>
const int N=(int )1e6+,mod=(int) 1e9;
inline int read(void ){
int s=;char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<='') s=s*+(ch^),ch=getchar();
return s;
} int n,m,k;
int x[N],y[N],z[N],g[N],f[N];
inline int find(int x){
if(x==f[x]) return x;
int t=find(f[x]);g[x]^=g[f[x]];
return f[x]=t;
}
inline int solve()
{
for(int i=;i<=n+m;i++) f[i]=i,g[i]=;
f[n+]=;
for (int i=;i<=k;i++)
{
int u=find(x[i]),v=find(y[i]+n),t=g[x[i]]^g[y[i]+n]^z[i];
if (u!=v) f[u]=v,g[u]=t;
else if (t) return ;
}
int sum=;
for (int i=;i<=n+m;i++)
if (f[i]==i)
if (!sum) sum=;
else {
sum<<=;
sum-=mod*(sum>mod);
}
return sum;
}
int main(){
bool e[]={,};
n=read(),m=read(),k=read();
for(int i=;i<=k;i++){
x[i]=read(),y[i]=read(),z[i]=read();
if(!((x[i]^)|(y[i]^))){
e[z[i]]=,i--,k--;continue;
}
if(!((x[i]|y[i])&)) z[i]^=;
}
int ans=;
if(e[]) ans=solve();
if(e[]){
for(int i=;i<=k;i++)
if((x[i]^)&&(y[i]^)) z[i]^=;
ans+=solve();
ans-=(ans>mod)*mod;
}
printf("%d\n",ans);
}
//承认抄代码。。
