Codeforces 578F Mirror Box

题目大意

一个 $n\times m$ 个格子的网格图,有些格子上有双面的镜子,有些格子上没有。镜子都是呈对角线放置( /\ )。
现在你要在所有没有镜子的格子上摆放镜子,使得最后网格图满足下面两个条件:
$\bullet$ 从网格图边界上的任意一条边垂直向内射入光线,光线一定会从一条相邻边射出网格图。
$\bullet$ 对于网格图的中的任意一条边,都存在一种从边界处一条边垂直向内射入光线的方法,使得这条边被光线穿过。
求满足条件的摆放镜子的方案数。答案对 $P$ 取模。

$1\leq n,m\leq100,3\leq P\leq10^9+7,P\in\mathbb{P}$
空白格子个数 $K$ 不超过 $200$。


题目分析

将格点黑白染色。可以发现,条件一中的光线围住的边界点颜色一定是一致的。
我们不妨假设要围住黑点。考虑将镜子看成无向边,既然光线会围住黑点,那么黑点一定是不连通的。
考虑条件二,每一条边都要被光线穿过,其实就是要求图不存在环。
那么白点又会形成什么呢?不妨在图的外面再加上一圈的镜子使得条件一中的光线实际上构成一个回路,可以发现这条回路穿过了网格图中的所有边,并且是一个简单环。假设白点不连通,那么一定是存在一条黑点构成的路径从一侧边界穿到了另一侧,这样显然不能满足前面的条件。因此白点实质上构成了一棵生成树。
剩下的问题就很简单了,由于空白格子最多只有 $200$,直接基尔霍夫矩阵树定理求白点生成树个数就好了。
对于围住白色的情况同理,再做一次类似过程就可以解决。
时间复杂度 $O(K^3)$。


代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
const int N=105;
const int T=205;
const int S=N*N;
const int V=T<<1;
int fa[S],lab[S];
char MAP[N][N];
int n,m,s,P,idx,ans;
bool cir=0;
inline int quick_power(int x,int y)
{
int ret=1;
for (;y;y>>=1,x=1ll*x*x%P) if (y&1) ret=1ll*ret*x%P;
return ret;
}
int getfather(int son){return fa[son]==son?son:fa[son]=getfather(fa[son]);}
inline bool merge(int x,int y)
{
x=getfather(x),y=getfather(y);
if (x==y) return 0;
return fa[y]=x,1;
}
struct matrix
{
int num[V][V];
int n;
inline void init(int n_=0)
{
n=n_;
for (int i=0;i<n;++i)
for (int j=0;j<n;++j)
num[i][j]=0;
}
inline int det()
{
bool sig=1;
for (int i=0;i<n;++i)
{
if (!num[i][i])
for (int j=i+1;j<n;++j)
if (num[j][i])
{
sig^=1;
for (int k=0;k<n;++k) swap(num[i][k],num[j][k]);
break;
}
if (num[i][i])
for (int j=i+1,inv=quick_power(num[i][i],P-2);j<n;++j)
if (num[j][i])
for (int k=0,mul=1ll*num[j][i]*inv%P;k<n;++k)
(num[j][k]+=P-1ll*num[i][k]*mul%P)%=P;
}
int ret=1;
for (int i=0;i<n;++i) ret=1ll*ret*num[i][i]%P;
return sig>0?ret:P-ret;
}
}Kir;
inline int getid(int x,int y){return x*(m+1)+y;}
inline void addedge(int x,int y){(++Kir.num[x][x])%=P,(++Kir.num[y][y])%=P,(Kir.num[x][y]+=P-1)%=P,(Kir.num[y][x]+=P-1)%=P;}
int main()
{
freopen("mirror.in","r",stdin),freopen("mirror.out","w",stdout);
scanf("%d%d%d",&n,&m,&P),s=(n+1)*(m+1);
for (int x=0;x<s;++x) fa[x]=x;
for (int i=0;!cir&&i<n;++i)
{
scanf("%s",MAP[i]);
for (int j=0;!cir&&j<m;++j)
if (MAP[i][j]=='/') cir|=!merge(getid(i+1,j),getid(i,j+1));
else if (MAP[i][j]=='\\') cir|=!merge(getid(i,j),getid(i+1,j+1));
}
if (cir) printf("0\n");
else
{
for (int x=0;x<s;++x) lab[x]=-1;
idx=0;
for (int i=0,x;i<=n;++i)
for (int j=0;j<=m;++j)
if ((i^j^1)&1)
{
x=getid(i,j);
if (getfather(x)==x) lab[x]=idx++;
}
Kir.init(idx);
for (int i=0;i<n;++i)
for (int j=0;j<m;++j)
if (MAP[i][j]=='*')
if ((i^j^1)&1) addedge(lab[fa[getid(i,j)]],lab[fa[getid(i+1,j+1)]]);
else addedge(lab[fa[getid(i+1,j)]],lab[fa[getid(i,j+1)]]);
--Kir.n,ans=Kir.det();
for (int x=0;x<s;++x) lab[x]=-1;
idx=0;
for (int i=0,x;i<=n;++i)
for (int j=0;j<=m;++j)
if ((i^j)&1)
{
x=getid(i,j);
if (getfather(x)==x) lab[x]=idx++;
}
Kir.init(idx);
for (int i=0;i<n;++i)
for (int j=0;j<m;++j)
if (MAP[i][j]=='*')
if ((i^j)&1) addedge(lab[fa[getid(i,j)]],lab[fa[getid(i+1,j+1)]]);
else addedge(lab[fa[getid(i+1,j)]],lab[fa[getid(i,j+1)]]);
--Kir.n,(ans+=Kir.det())%=P,printf("%d\n",ans);
}
fclose(stdin),fclose(stdout);
return 0;
}