题意

有一个 $n \times n$ 的网格，初始时有 $k$ 个位置给定了字符 x 或 o 中的一种，其他的默认为空。现在问有多少种填格子方案使得对于每个格子，它四联通相邻的格子的 o 的数量都是偶数。对 $10^9+7$ 取模。

$1 \leq n,k \leq 10^5$

题解

首先我们发现确定了第一行就能确定整个格子长什么样：我们设 o 为 $1$，x 为 $0$，那么相当于要求每个格子周围格子的异或和都是 $0$。也就可以得到 $a_{i,j} = a_{i-1,j-1} \oplus a_{i-1,j+1} \oplus a_{i-2,j}$。

由于现在是钦定一些格子的取值，我们自然去思考是否能将某个格子快速表示为第一行的一些格子的值的异或。打表发现：

$a_{i,j}$ 的值是第一行第 $|i-j|+1,|i-j|+3,\ldots,|i-j|+2r-1$ 列的格子决定，其中 $r$ 是 $(i,j)$ 到边界的最短距离（也就是 $\min(i,j,n-i+1,n-j+1)$）。

所以我们 $a_{1,*}$ 按照奇偶性分类，相当于就是限制某个区间内的变量的异或和是 $1$ 或是 $0$ 求方案数。

看到区间，想到差分，问题就变成了限制某两个点的异或和是 $1$ 或 $0$ 求方案数了。注意这里有个细节是差分的时候要加入一个 $s_0$，这里是强制 $s_0=0$ 的，后面算方案的时候要特判一下这个地方。

然后现在问题就变成：有一些关系，每个关系形如某一对 $01$ 变量要求相同或不同，求方案数。

这是个经典问题：我们先把相同的缩成一个点，然后对于每一个不同的限制，在它们对应的点之间连边。如果这个图不是一个二分图（或者有自环）显然无解，否则答案和联通块个数有关：每个不包含 $s_0$ 的联通块对答案的贡献都是 $2$。设所有的联通块个数为 $s$，答案就是 $2^{s-2}$。

这个题提示我们：看到「奇数」，「偶数」，也可以想到异或，然后去找一下关系。

代码

#include <bits/stdc++.h>

#define fi first
#define se second
#define DB double
#define U unsigned
#define P std::pair
#define LL long long
#define LD long double
#define pb emplace_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e5 + 5;
const int ha = 1e9 + 7;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

struct DS{
    int f[MAXN],n;

    inline void init(int sz){
        n = sz;FOR(i,0,n) f[i] = i;
    }

    inline int find(int x){
        return x == f[x] ? x : f[x] = find(f[x]);
    }

    inline void merge(int x,int y){
        x = find(x);y = find(y);
        if(x == y) return;
        f[x] = y;
    }

    inline int size(){
        int sz = 0;
        FOR(i,0,n) if(find(i) == i) sz++;
        return sz;
    }
}f1,f2;
std::vector<P<int,int> > e1,e2;

int n,k;
std::vector<int> G1[MAXN],G2[MAXN];

inline int ctoi(char c){
    if(c == 'o') return 1;
    return 0;
}

int col[MAXN];bool vis[MAXN];

inline void dfs1(int v,int fa=0){
    vis[v] = 1;
    for(auto x:G1[v]){
        if(x == fa) continue;
        if(!vis[x]) col[x] = col[v]^1,dfs1(x,v);
        else if(col[x]==col[v]){puts("0");exit(0);}
    }
}

inline void dfs2(int v,int fa=0){
    vis[v] = 1;
    for(auto x:G2[v]){
        if(x == fa) continue;
        if(!vis[x]) col[x] = col[v]^1,dfs2(x,v);
        else if(col[x]==col[v]){puts("0");exit(0);}
    }
}

int main(){
    scanf("%d%d",&n,&k);
    if(n == 1) return puts(k?"1":"2"),0;
    f1.init((n+1)/2);f2.init(n/2);
    FOR(i,1,k){
        int x,y;char str[5];scanf("%d%d%s",&x,&y,str);
        int c = ctoi(str[0]);
        int l = std::abs(x-y)+1,r = l+2*(std::min({x,y,n-x+1,n-y+1})-1);
        if(l&1){
            l = (l+1)>>1;r = (r+1)>>1;
            if(c){// s[l-1] != s[r]
                e1.pb(l-1,r);
            }
            else{// s[l-1] == s[r]
                f1.merge(l-1,r);
            }
        }
        else{
            l >>= 1;r >>= 1;
            if(c){
                e2.pb(l-1,r);
            }
            else{
                f2.merge(l-1,r);
            }
        }
    }
    for(auto x:e1){
        int u = f1.find(x.fi),v = f1.find(x.se);
        if(u == v) return puts("0"),0;
        G1[u].pb(v);G1[v].pb(u);
    }
    for(auto x:e2){
        int u = f2.find(x.fi),v = f2.find(x.se);
        if(u == v) return puts("0"),0;
        G2[u].pb(v);G2[v].pb(u);
    }
    int t = 0;
    FOR(i,0,n) if(i == f1.find(i) && !vis[i]) dfs1(i),++t;
    CLR(vis,0);CLR(col,0);
    FOR(i,0,n) if(i == f2.find(i) && !vis[i]) dfs2(i),++t;
    printf("%d\n",qpow(2,t-2));
    return 0;
}