Codeforces

Luogu

分析

我们把顶点黑白染色，那么一面镜子就可以看成是连接同色点的一条边。

接下来给出一个结论：一个方案合法当且仅当黑点连成了一棵树或者白点连成了一棵树。

（比较感性理解的）证明：

• 首先，当黑点连边确定时白点连边一定唯一确定，所以我们只考虑黑边确定的情况。
• 先证必要性：
  • 先考虑后面那个限制。如果连成了环，则环内部的边一定没有光线会穿过，所以不能有环。
  • 再考虑前面那个限制。我们需要用一些边把边界划分成若干个长度为 $2$ 的段，可以发现如果不连通的话则一定无法完成，所以必须连通。
• 再证充分性（懒得证了）

于是我们只需要求生成树个数，矩阵树定理。

有一个小问题是点数是 $\mathcal{O}(nm)$ 的。但是有很多边是已经确定了的，所以可以直接缩起来，点数就变成 $\mathcal{O}(k)$ 的了。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000+10;
int mod;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int n,m; char s[N][N];
int id[N][N],pos[N*N],f[N*N],tot=0;
int find(int x) { return f[x]==x?x:f[x]=find(f[x]); }
void merge(int x,int y) { x=find(x),y=find(y); if (x!=y) f[x]=y; }

struct Graph {
    int n,C[N][N];
    Graph() { n=0,memset(C,0,sizeof(C)); }
    void add(int u,int v) { ++C[u][u],++C[v][v],--C[u][v],--C[v][u]; }
    int Gauss(int n) {
        for (int i=1;i<=n;++i)
            for (int j=1;j<=n;++j) C[i][j]=(C[i][j]+mod)%mod;
        int ans=1;
        for (int i=1;i<=n;++i) {
            if (!C[i][i]) {
                for (int j=i+1;j<=n;++j)
                    if (C[j][i]) { swap(C[i],C[j]),ans=mod-ans; break; }
            }
            ans=1ll*ans*C[i][i]%mod;
            int inv=qpow(C[i][i],mod-2);
            for (int j=i+1;j<=n;++j) {
                int t=1ll*C[j][i]*inv%mod;
                for (int k=1;k<=n;++k)
                    C[j][k]=(C[j][k]-1ll*t*C[i][k]%mod+mod)%mod;
            }
        }
        return ans;
    }
} G[2];

int main() {
    n=read(),m=read(),mod=read();
    for (int i=1;i<=n;++i) scanf("%s",s[i]+1);
    for (int i=1;i<=n+1;++i)
        for (int j=1;j<=m+1;++j) id[i][j]=++tot,f[tot]=tot;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j) {
            if (s[i][j]=='/') merge(id[i+1][j],id[i][j+1]);
            if (s[i][j]=='\\') merge(id[i][j],id[i+1][j+1]);
        }
    for (int i=1;i<=n+1;++i)
        for (int j=1;j<=m+1;++j)
            if (find(id[i][j])==id[i][j]) pos[id[i][j]]=++G[(i+j)&1].n;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j) {
            if (s[i][j]!='*') continue;
            G[(i+j)&1].add(pos[find(id[i][j])],pos[find(id[i+1][j+1])]);
//          debug("%d add (%d,%d)\n",(i+j)&1,pos[find(id[i][j])],pos[find(id[i+1][j+1])]);
            G[(i+j)&1^1].add(pos[find(id[i+1][j])],pos[find(id[i][j+1])]);
//          debug("%d add (%d,%d)\n",(i+j)&1^1,pos[find(id[i+1][j])],pos[find(id[i][j+1])]);
        }
    printf("%d\n",(G[0].Gauss(G[0].n-1)+G[1].Gauss(G[1].n-1))%mod);
    return 0;
}