\(\text{Problem}:\)Mirror Box
\(\text{Solution}:\)
较为显然的是如果 / 和 \ 围出了一个环，就无解。
考虑光线会从相邻的边界段射出，这说明两个边界段的奇偶性相同的非重合端点（此处认为一个网格上点 \((i,j)\) 的奇偶性为 \((i+j)\%2\) 的取值，原图有 \((n+1)\times(m+1)\) 个点）被 / 和 \ 相连。
而上面连通的点 \((i_{1},j_{1}),(i_{2},j_{2})\) 的奇偶性相同，且 / 和 \ 连接的两点奇偶性也相同，这提示在合法的网格中，奇数点或偶数点相连形成一棵树。而当网格图上的 * 被确定时，一定不存在奇数点和偶数点能同时形成一棵树，原因显然。这提示我们对奇数点和偶数点分别算出答案，相加即可。
现在考虑有 * 的情况。不难发现，将已确定连通的点缩点后，可以把网格图转化为两张无向图，需要对每张无向图求出生成树个数。利用矩阵树定理即可求解。
注意首先要判断给定的 / 和 \ 是否已经构成环，以及奇数点图与偶数点图是否连通。若满足以上情况，对应的奇数点图或偶数点图的答案显然为 \(0\)。时间复杂度 \(O(nm\cdot\alpha(nm)+K^3)\)。
\(\text{Code}:\)
#include <bits/stdc++.h>
//#pragma GCC optimize(3)
//#define int long long
#define ri register
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define is insert
#define es erase
#define vi vector<int>
#define vpi vector<pair<int,int>>
using namespace std; const int N=210;
inline int read()
{
int s=0, w=1; ri char ch=getchar();
while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
return s*w;
}
int n,m,Mod; char s[N][N];
int f[N*N],id[N*N],cnt,a[N][N];
inline int Id(int x,int y) { return (x-1)*(m+1)+y; }
inline void Init()
{
for(ri int i=1;i<=n+1;i++)
for(ri int j=1;j<=m+1;j++)
f[Id(i,j)]=Id(i,j);
}
inline int Find(int x) { return f[x]^x?f[x]=Find(f[x]):x; }
inline void Merge(int x,int y)
{
int fx=Find(x), fy=Find(y);
if(fx==fy) { puts("0"); exit(0); }
f[fx]=fy;
}
inline int Det()
{
int res=1;
for(ri int i=1;i<cnt;i++)
{
for(ri int j=i+1;j<cnt;j++)
{
while(a[i][i])
{
int w=a[j][i]/a[i][i];
for(ri int k=i;k<cnt;k++) a[j][k]=(a[j][k]-1ll*w*a[i][k]%Mod+Mod)%Mod;
for(ri int k=1;k<cnt;k++) swap(a[i][k],a[j][k]);
res=-res;
}
for(ri int k=1;k<cnt;k++) swap(a[i][k],a[j][k]);
res=-res;
}
}
for(ri int i=1;i<cnt;i++) res=1ll*res*a[i][i]%Mod;
return (res+Mod)%Mod;
}
inline int Solve(int tp)
{
cnt=0;
memset(a,0,sizeof(a));
for(ri int i=1;i<=n+1;i++)
{
for(ri int j=1;j<=m+1;j++)
{
if((i+j)%2==tp && Id(i,j)==Find(Id(i,j))) id[Id(i,j)]=++cnt;
}
}
for(ri int i=1;i<=n;i++)
{
for(ri int j=1;j<=m;j++)
{
if(s[i][j]=='*')
{
int x,y;
if((i+j)%2==tp) x=id[Find(Id(i,j))], y=id[Find(Id(i+1,j+1))];
else x=id[Find(Id(i+1,j))], y=id[Find(Id(i,j+1))];
if(x==y) continue;
a[x][x]++, a[y][y]++, a[x][y]--, a[y][x]--;
}
}
}
return Det();
}
signed main()
{
n=read(), m=read(), Mod=read();
for(ri int i=1;i<=n;i++) scanf("%s",s[i]+1);
Init();
for(ri int i=1;i<=n;i++)
{
for(ri 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));
}
}
printf("%d\n",(Solve(0)+Solve(1))%Mod);
return 0;
}