题目
给你一个n*n网格,每一格要么是0要么是1要么为空,要求你用0或1填满所有空格,使得每个格子周围的0有偶数个。
题解
首先我们观察到这样一个事实:当第一行确定后,整个网格的填法就确定了。我们以N=8为例,把这种确定方法列出来:其中,“0246”这样的数的含义为,假设第一行为a[0..7],它表示该格的值是a[0] xor a[2] xor a[4] xor a[6].
可以发现,这个形式是很规整的。都是“246”或者“1357”这种,连续的奇/偶数。
因此,我们的问题就变成了:问有多少种a的取值,满足K组形如a[1] xor a[3] xor a[5] xor a[7] = 1(或者0)这样的限制。
不妨设a的“奇/偶前缀和”为s,就是说s[6] = a[0] xor a[2] xor a[4],s[5] = a[0] xor a[3],等等。那么a[1] xor a[3] xor a[5] xor a[7] = 1这个限制就变成了s[1] xor x[9] = 1.可以发现,所有对a的“段”限制都变成了s中某两个数的限制:它们要么相等要么相反。
这就变成了一道有成熟算法的题目:让每个s[i]都对应两个元素i和i’,二者的值相反。对于s[a] xor s[b] = 0这种限制,就把a和b,a’和b’放在同一个并查集中;对于s[a] xor s[b] = 1这种限制,就把a和b’,a’和b放在同一个并查集中。如果在某个时刻,某个a和a’被并在了一起,则无解。
设最后剩下的等价类数量是cnt,可以发现,其中有4个的值是确定的:s[0]和s[1],以及它们的反。因此,答案就是2^((cnt-4)/2).
代码
#include#include #include #include using namespace std; const int SIZEN=100010; const int MOD=1000000007; int pow2(int n){ int ans=1; for(int i=1;i<=n;i++){ ans=(ans<<1)%MOD; } return ans; } class EQ2{//solver public: int ufs[SIZEN*2]; void clear(void){ memset(ufs,-1,sizeof(ufs)); } EQ2(){clear();} int grand(int x){ return ufs[x]==-1?x:ufs[x]=grand(ufs[x]); } bool merge(int a,int b){//元素a和元素b int ga=grand(a),gb=grand(b); if(grand(a^1)==gb) return false; if(grand(b^1)==ga) return false; if(ga!=gb) ufs[ga]=gb; return true; } bool test(int a,int b,int t){//变量a和变量b的xor是t if(t==0){ return merge(2*a,2*b)&&merge(2*a+1,2*b+1); } else if(t==1){ return merge(2*a,2*b+1)&&merge(2*a+1,2*b); } } int count(int N){//0~N N=2*N+1; int ans=0; for(int i=0;i<=N;i++){ if(grand(i)==i) ans++; } return ans; } }S; void work(void){ int N,K,a,b,p; char ch[10]; scanf("%d%d",&N,&K); for(int i=1;i<=K;i++){ scanf("%d%d",&a,&b); a--,b--; scanf("%s",ch); p=(ch[0]=='x'?0:1); int l=abs(a-b); int r=min(a+b,2*(N-1)-(a+b)); if(!S.test(l,r+2,p)){ printf("0\n"); return; } } int cnt=S.count(N+1); printf("%d\n",pow2((cnt-4)/2)); } int main(){ //freopen("input.in","r",stdin); work(); return 0; }