OI - 白金元首与独舞(洛谷) | Lucky_Glass's Blog
0%

OI - 白金元首与独舞(洛谷)

冬令营变成夏令营然后被咕掉了:(


# 题意

点击展开/折叠题意

元首把花园分为 $n$ 行 $m$ 列的网格。每个格子中都可以放置一个标识,指向上、下、左、右四个方向中的任意一个。元首位于一个格子时,会按照其中标识所指的方向进入周围的格子,或者走出花园(即目的格子不在网格之内)。

元首已经设计好了大部分格子的标识。元首用字符 L、R、U、D 分别表示指向左、右、上、下四个方向的标识,用字符 . 表示未决定的格子。现在,元首希望将每个 . 替换为 L、R、U、D 中任意一种,使得从花园中的任意一个格子出发,按照上述规则行走,都可以最终走出花园。

你需要编写程序帮助元首计算替换的不同方案数。两个方案不同当且仅当存在一个格子,使得两个方案中该格子内的标识不同。当然,由于答案可能很大,只需给出方案数除以 $10^9 + 7$ 所得的余数即可。


# 解析

我们把方格之外的点看作一个整体,作为“格子0”。然后根据方格上的 LRDU 来给格点之间连接有向边。

然后我们就要给原来是 . 的格子填上 LRDU,使得最后每个点沿着有向边走都能到达方格外的格子0。

发现每个格点的出边只有一条,那么就是要求以格点0为根的内向树。直接用 Matrix-Tree 定理,但是点数太多($O(nm)$),能不能有一些不储存?

因为原来有一些格子已经是 LRDU 了,那么它的出边就固定了。也就是说原图上已经形成了一个有根树森林,则对于一个有根树,我们可以用它的“根格子”来代表它。

当然可能存在不是有根树,而是有环的情况,直接特判输出0。

考虑无环,那么所有有根树的根要么是格点0(走出了方格),要么是一个 . 格点。由于 . 格点只有 100 个,那么点数就是 101,就可以用 Matrix-Tree 了。

Tab. 处理初始的有根树森林可以用并查集


# 源代码

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=304,MOD=1e9+7;
const int DIR[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

#define cs const int &
inline int Add(cs a,cs b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(cs a,cs b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(cs a,cs b){return 1ll*a*b%MOD;}
inline int Pow(int a,int b){int r=1;while(b){if(b&1)r=Mul(r,a);a=Mul(a,a);b>>=1;}return r;}

struct DSU{
int fa[N*N];
int Find(int u){return fa[u]==u?u:fa[u]=Find(fa[u]);}
bool Merge(int u,int v){
u=Find(u),v=Find(v);
if(u==v) return false;
fa[u]=v;
return true;
}
void Init(int siz){for(int i=0;i<=siz;i++) fa[i]=i;}
}Ds;

int n,m;
int mat[N][N],imap[N*N];
char maz[N][N];

inline int Idx(int x,int y){return (x<1 || x>n || y<1 || y>m)?0:(x-1)*m+y;}
void Link(int ux,int uy,int vx,int vy){
int u=Idx(ux,uy),v=Idx(vx,vy);
Ds.Merge(u,v);
}
int Calc(int siz){
int ret=1;
for(int i=1;i<=siz;i++){
int it=-1;
for(int j=i;j<=siz;j++)
if(mat[j][i]){
it=j;
break;
}
if(it==-1) return 0;
if(it!=i){
ret=Sub(0,ret);
for(int j=i;j<=siz;j++) swap(mat[i][j],mat[it][j]);
}
ret=Mul(ret,mat[i][i]);
int dv=Pow(mat[i][i],MOD-2);
for(int j=i;j<=siz;j++) mat[i][j]=Mul(mat[i][j],dv);
for(int j=i+1;j<=siz;j++){
if(!mat[j][i]) continue;
int mul=mat[j][i];
for(int k=i;k<=siz;k++) mat[j][k]=Sub(mat[j][k],Mul(mat[i][k],mul));
}
}
return ret;
}
int main(){
int cas;scanf("%d",&cas);
while(cas--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%s",maz[i]+1);
Ds.Init(n*m+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
imap[Idx(i,j)]=-1;
switch(maz[i][j]){
case 'L': Link(i,j,i,j-1);break;
case 'R': Link(i,j,i,j+1);break;
case 'U': Link(i,j,i-1,j);break;
case 'D': Link(i,j,i+1,j);break;
}
}
bool fai=false;
for(int i=1;i<=n && !fai;i++)
for(int j=1;j<=m;j++){
int it=Ds.Find(Idx(i,j));
if(it){
it--;
int x=it/m+1,y=it%m+1;
if(maz[x][y]!='.'){
fai=true;
break;
}
}
}
if(fai){printf("0\n");continue;}
int siz=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(maz[i][j]=='.'){
for(int k=0;k<4;k++){
int x=i+DIR[k][0],y=j+DIR[k][1];
int u=Idx(i,j),v=Ds.Find(Idx(x,y));
if(imap[u]==-1) imap[u]=++siz;
if(imap[v]==-1) imap[v]=++siz;
u=imap[u],v=imap[v];
mat[u][u]=Add(mat[u][u],1);
mat[u][v]=Sub(mat[u][v],1);
}
}
printf("%d\n",Calc(siz));
for(int i=0;i<=siz;i++)
for(int j=0;j<=siz;j++)
mat[i][j]=0;
}
return 0;
}

THE END

Thanks for reading!