[CF 461D] Appleman and Complicated Task

作法：

首先把所有格子以$x+y$的奇偶性分成兩類，這兩類可以分開處理，因為題目給的條件中當某個格子的顏色改變的時候，不會影響到所有和他不同類的格子是否滿足條件。再來注意到，考慮把白色賦值成$1$，黑色則為$0$，那麼題目的條件就變成：對於每一個$(i,j)$，$c_{i-1,j}\; xor \; c_{i,j-1}\; xor \; c_{i,j+1} \; xor \; c_{i+1,j}=0$，其中$c_{i,j}$代表$(i,j)$的顏色的值。而$xor$可以看成二進制下的加法，所以可以把條件改寫成$c_{i-1,j}+c_{i,j-1}+ c_{i,j+1}+ c_{i+1,j}=0$，或是$c_{i-1,j}=c_{i,j-1}+ c_{i,j+1}+ c_{i+1,j}$。以下稱第一類格子為$x+y$值為奇數的，第二類則是偶數的。接下來我們先只考慮第一類格子，可以發現到當正方形中的主對角線旁邊的兩排格子的顏色都確定後，整個盤面上的所有第一類格子的值都確定了，所以只要確定好這兩排的值就好了（他們就是$x,y$座標差$1$的格子們）。並且由$(1,1)$的條件限制可得$c_{1,2}=c_{2,1}$，再由$(2,2)$的條件限制得$c_{2,3}=c_{3,2}$，一直推下去就可以得到$c_{i,i+1}=c_{i+1,i}$了。因此接下來記$C_i=c_{i,i+1}$，那麼我們想要知道：當題目給了一個限制條件$c_{x,y}$是$0$或$1$的時候（他是第一類格子），會對$C_i$造成什麼限制。

上圖中代表每一格分別是由哪些$C_i$所$xor$出來的，這樣可以發現一個規律：$(i,j)$會是由$C_{\frac{i-j-1}{2}}$和$C_{\frac{i+j-1}{2}}$所$xor$出來的，並且再觀察$(7,5)$的限制條件，會得到$C_1=C_6$，還有$(7,3),(7,1)$的限制條件分別可以得到$C_2=C_5$和$C_3=C_4$，而這也是蠻顯然的條件，因為整個盤面會對兩條對角線對稱。因此一般來說，必須要有$C_{i}=C_{n-i}$。由上圖可推得，當我們得到了「$c_{x,y}$是多少」的條件時，其實就等於獲得了$C_p\; xor \; C_q$等於多少，也就是他們兩個是否相等的條件。並且當給定的$(x,y)$本身就是$C_i$的一員時條件就變成「$C_i$等於多少」。因此這樣就轉換成經典問題了：給定一張圖，跟其中一些節點的顏色，並且給定許多「某兩個點同色」和「某兩個點異色」的條件，問共有幾種塗法。而這只要對每個連通塊分開做，並把所有答案乘起來。並且當某個連通塊不滿足那些條件限制時答案為$0$，否則當這個連通塊中已經有某個點的顏色確定的話答案為$1$，如果沒有的話就是$2$。

至於第二類格子的處理和上面類似，這時是只要決定主對角線上的顏色就好了，並且一樣記$C_i=c_{i,i}$，那麼這次可以得到$(i,j)$會是由$C_{\frac{i-j}{2}}$和$C_{\frac{i+j}{2}}$所$xor$出來的，並且一樣有盤面對稱的條件，也就是$C_{i}=C_{n+1-i}$，之後的處理就和前面一模一樣了。

code :

#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
const int maxn=100000+10 ;
void err(){printf("0\n") ; exit(0) ;}
 
struct P{int to,dis;};
vector<P> v[2][maxn] ;
 
int fa[2][maxn],fad[2][maxn] ;
int getfa(int id,int x)
{
    if(fa[id][x]==x) return x ;
    int f=fa[id][x] , t=getfa(id,f) ;
    fad[id][x]=(fad[id][x]+fad[id][f])%2 ;
    return fa[id][x]=t ;
}
 
bool join(int x,int y,int id,int dis)
{
    v[id][x].push_back((P){y,dis}) ;
    v[id][y].push_back((P){x,dis}) ;
    int x2=getfa(id,x) , y2=getfa(id,y) ;
    dis=(dis+fad[id][x]+fad[id][y])%2 ;
    if(x2!=y2)
    {
        fa[id][x2]=y2 ; fad[id][x2]=dis ;
        return 1 ;
    }
    else return dis==0 ;
}
 
int col[2][maxn] ;
bool vis[2][maxn] ;
bool dfs(int id,int x,int c)
{
    vis[id][x]=1 ; col[id][x]=c ;
    for(auto i : v[id][x])
    {
        int c2=col[id][i.to] ;
        if(c2!=-1 && c2!=(c^i.dis)) return 0 ;
        if(!vis[id][i.to] && !dfs(id,i.to,c^i.dis))
            return 0;
    }
    return 1 ;
}
 
main()
{
    int n,k ; scanf("%d%d",&n,&k) ;
    memset(col,-1,sizeof(col)) ;
    for(int i=0;i<2;i++) for(int j=1;j<=n;j++)
        fa[i][j]=j ;
    for(int i=1;i<n-i;i++) join(i,n-i,0,0) ;
    for(int i=1;i<n+1-i;i++) join(i,n+1-i,1,0) ;
 
    while(k--)
    {
        int a,b,di ; char c[3] ;
        scanf("%d%d%s",&a,&b,c) ;
        di=(c[0]=='o' ? 1 : 0) ;
        if(a>b) swap(a,b) ;
        if((a+b)%2)
        {
            int x=(b-a-1)/2 , y=(a+b-1)/2 ;
            if(!x)
            {
                if(col[0][a]!=-1 && col[0][a]!=di) err() ;
                col[0][a]=di ; continue ;
            }
            if(!join(x,y,0,di)) err() ;
        }
        else
        {
            int x=(b-a)/2 , y=(a+b)/2 ;
            if(!x)
            {
                if(col[1][a]!=-1 && col[1][a]!=di) err() ;
                col[1][a]=di ; continue ;
            }
            if(!join(x,y,1,di)) err() ;
        }
    }
 
    int ans=1 ;
    for(int z=0;z<2;z++)
    {
        int n2=(z==0 ? n-1 : n) ;
        for(int i=1;i<=n2;i++)
            if(col[z][i]!=-1 && !vis[z][i]
               && !dfs(z,i,col[z][i])) err() ;
        for(int i=1;i<=n2;i++) if(!vis[z][i])
        {
            if(!dfs(z,i,0)) err() ;
            ans=ans*2%MOD ;
        }
    }
    printf("%d\n",ans) ;
}