正題

題目鏈接:https://www.luogu.com.cn/problem/CF461D

---

題目大意

$n?n$的網格需要填上$x$或$o$，其中有$k$個格子已經固定，求有多少中填寫方案使得每個格子的四周都有偶數個$o$。

---

解題思路

約束條件相當于一個格子周圍的異或和都為$0$，也就是對于任意$(x,y)$都有$a_{x?1,y}xor{a}_{x,y?1}xor{a}_{x+1,y}xor{a}_{x,y+1}$。也就是對于一個格子$(x,y)$也有$a_{x,y}=a_{x?1,y?1}xor{a}_{x?1,y+1}xor{a}_{x?2,y}$

根據以上我們可以發現對于一個格子的值都可以由第一行的某些格子的異或和來表示，且它們格子的奇偶相同。

從這個藍色格子來看，它的值等于黃色格子和青色格子的異或和。

其中兩個黃色格子又都包括了青色格子，所以相互抵消，中間缺失的青色格子回本藍色本身補回來，而周圍的綠色格子不會被抵消。

所以能夠發現其實藍色格子的異或和就等于某一行里被紅線夾著的同奇偶的格子的異或和。

這樣我們對于一個固定的點就相等于限制奇或偶的一個區間異或值。

差分完之后就變為了判斷兩個格子是否相等，用并查集判即可。

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2e5+10; const long long P=1e9+7,inv2=(P+1)/2; int n,k,fa[N]; int find(int x) {return (fa[x]==x)?x:(fa[x]=find(fa[x]));} bool Calc(int l,int r,int w){if(w){if(find(l)==find(r))return 0;if(find(l)==find(r+n))return 1;fa[find(r+n)]=find(l);fa[find(l+n)]=find(r);}else{if(find(l)==find(r+n))return 0;if(find(l)==find(r))return 1;fa[find(r)]=find(l);fa[find(r+n)]=find(l+n);}return 1; } int main() {scanf("%d%d",&n,&k);int p=n;n+=2;for(int i=1;i<=2*n;i++)fa[i]=i;for(int i=1;i<=k;i++){int x,y;char w[2];scanf("%d%d%s",&x,&y,&w);x--;y--;int l=abs(x-y),r=min(x+y,2*(p-1)-x-y)+2;if(!Calc(l,r,w[0]=='o'))return puts("0")&0;}long long ans=inv2*inv2%P,z=0;for(int i=0;i<2*n;i++)if(find(i)==i)z++;z/=2;while(z)z--,ans=ans*2%P;printf("%lld\n",ans);return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的CF461D-Appleman and Complicated Task【并查集】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。