外包网络推广公司推广网站/建站模板网站

2303: [Apio2011]方格染色

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 2309  Solved: 879
[Submit][Status][Discuss]

Description

Sam和他的妹妹Sara有一个包含n × m个方格的
表格。她们想要将其的每个方格都染成红色或蓝色。
出于个人喜好，他们想要表格中每个2 ×   2的方形区
域都包含奇数个（1 个或 3 个）红色方格。例如，右
图是一个合法的表格染色方案（在打印稿中，深色代
表蓝色，浅色代表红色） 。 
可是昨天晚上，有人已经给表格中的一些方格染上了颜色！现在Sam和Sara
非常生气。不过，他们想要知道是否可能给剩下的方格染上颜色，使得整个表格
仍然满足她们的要求。如果可能的话，满足他们要求的染色方案数有多少呢？ 

 

Input

输入的第一行包含三个整数n, m和k，分别代表表格的行数、列数和已被染
色的方格数目。 
之后的k行描述已被染色的方格。其中第 i行包含三个整数xi, yi和ci，分别
代表第 i 个已被染色的方格的行编号、列编号和颜色。ci为 1 表示方格被染成红
色，ci为 0表示方格被染成蓝色。 

Output

输出一个整数，表示可能的染色方案数目 W 模 10^9得到的值。（也就是说，如果 W大于等于10^9，则输出 W被10^9除所得的余数）。 

对于所有的测试数据，2 ≤ n, m ≤ 106
，0 ≤ k ≤ 10^6
，1 ≤ xi ≤ n，1 ≤ yi ≤ m。 
 

Sample Input

3 4 3
2 2 1
1 2 0
2 3 1

Sample Output

8

HINT

 

数据为国内数据+国际数据+修正版

 

鸣谢GYZ

 

思路：参考hzwer。几个性质：

一、如果确定了第一行，接下来的每一行只会是

       变换1.上一行所有奇数列异或1后得到

       变换2.上一列所有偶数列异或1后得到

二、判断无解的情况

       给定某一行的两列a，b颜色ca，cb，我们就可以得出第一行这两列同色（0）or反色（1）

      1.奇偶性相同的列（a mod 2 = b mod 2），第一行a，b列颜色关系为ca ^ cb

      2.奇偶性相同的列（a mod 2 <> b mod 2），设第一行到此行进行p1次变换1，p2次变换2

      则p1+p2=行号-1

      第一行a，b列颜色关系为cx^cy^（行号-1）（没理解，待补）

                                      对于fa[],vis[]数组的理解

第一种情况：蓝色的点是第一行的编号，D与A是在同一列，那么E的颜色就是唯一的

第二种情况：对于FG两个点，他们的关系是制约的，所以他们在一个联通块里，但是计算答案*2

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<string>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define SWAP(x,y,t) ( (t)=(x),(x)=(y),(y)=(t) )
const int p=1e9;
using namespace std;
int n,m,K,tot;
int fa[1000005],F[1000005],c[1000005];
bool mark[1000005],vis[1000005];
vector<int> r[1000005],col[1000005];
ll read()
{ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int qpow(ll a,ll b)
{ll ans=1;for(int i=b;i;i>>=1,a=(a*a)%p)if(i&1) ans=(ans*a)%p;return ans;
} 
int find(int x)
{return x==fa[x]?x:fa[x]=find(fa[x]);
}
int find2(int x)
{if(x==F[x]) return x;int tmp=find2(F[x]);c[x]^=c[F[x]];return F[x]=tmp;
}
bool add(int a,int b,int f)
{int p=find2(a),q=find2(b);if(p==q) return (c[a]^c[b])==f;else{F[p]=q;c[p]=(c[a]^c[b]^f);return 1;}
}
int main()
{n=read();m=read();K=read();for(int i=1;i<=m;i++) fa[i]=F[i]=i;for(int i=1;i<=K;i++){int a=read(),b=read(),c=read();if(a==1) vis[b]=1;mark[a]=1;r[a].push_back(b);col[a].push_back(c);}for(int i=1;i<=n;i++)for(int j=1;j<r[i].size();j++){int x=r[i][j],y=r[i][j-1],cx=col[i][j],cy=col[i][j-1];int p=find(x),q=find(y);fa[p]=q;if(vis[p]) vis[q]=1;//vis[]和fa[]表示是否与第一行相关int t=cx^cy;if(x%2!=y%2) t=(t^(i-1))&1;if(!add(x,y,t)){puts("0");return 0;}}for(int i=1;i<=m;i++) if(fa[i]==i&&vis[i]==0) tot++;for(int i=2;i<=n;i++) if(!mark[i]) tot++;printf("%d\n",qpow(2,tot));
}