「USACO 2021 US Open Platinum」Routing Schemes

Posted on Edited on In

「USACO 2021 US Open Platinum」Routing Schemes

\(K=0\)

此时，我们只需要求合法的匹配路径数量，并且一个路径是从小到大的

由于题目保证一定存在合法路径，从 \(1\) 到 \(n\) 考虑每一条 \((u,v),(v>u)\)

我们可以看成是很多个 \(S\) 在路径上被从 \(1-n\) 不断地推过去

设一个点的入度为

\(ind_v=\sum_{(u,v)} 1+[v为S]\)

\(outd_u=\sum_{(u,v)} 1+[u为R]\)

每次到达一个点，必然有其 \(ind_u=outd_u\) ，即推进来的 \(S\) 个数恰好等于出边个数

此时合法的分配这 \(outd_u\) 个 \(S\) 的方案数就是 \(outd_u!\)

直接求 \(\prod outd_i!\) 即可


\(K=1\)

存在反边的图看起来十分难处理，不妨直接把反边断掉

假设断掉前包含环的路径为 \(S_1\rightarrow a\rightarrow b\rightarrow R_1 (a>b)\)

则断掉后的路径变成 \(S_1\rightarrow a\) ， \(b\rightarrow R\)

不妨将在 \(a\) 上额外添加一个 \(R\) ，在 \(b\) 上额外添加一个 \(S\)

此时，新的问题又只包含 \((u,v)(u<v)\) ，同 \(K=0\) 求解

理想情况下，新问题中的所有方案均可以通过将 \(a,b\) 相接还原

但是显然如果最终方案上 \(b\rightarrow a\) 相接就会成环

所以需要额外 \(dp\) 出包含 \(b\rightarrow a\) 的非法方案

考虑用类似 \(K=0\) 的办法，我们扫描每个 \(i\) 将 \(S\) 向后推

令 \(dp_i\) 表示当前 \(dp\) 的路径最后一个点是 \(i\) 的方案数

我们希望结束点是 \(a\) ，开始点是 \(b\)

此时依次推过去 \(i\) ，此时只有 \(dp_{j},j\ge i\) 的情况是合法的

考虑 \(j=i\) 时，需要为 \(j\) 找一个归宿 \(k\) ，或者判定 \(j=a\) 时结束路径

此时，相当于在原图上使 \(outd_i\) 减少了 \(1\)

得到转移 \(dp_k\leftarrow dp_j\cdot (outd_i-1)!\)

当 \(j>i\) 时，不需要考虑 \(j\) 的变化

得到转移 \(dp_j\leftarrow dp_j\cdot outd_i!\)


\(K=2\)

有了 \(K=1\) 的铺垫，想必这里十分简单

设反边为 \((a,b),(c,d)\) ，显然加入两组 \(S,R\)

考虑新图上什么样的情况是不合法的

  1. \(b\rightarrow a\)

  2. \(d\rightarrow c\)

注意1,2是有交的

  1. \(b\rightarrow c\rightarrow d\rightarrow a\)

环交错扭在一起，这种情况比较容易漏掉

稍微容斥一下即可

复杂度分析：

扫描每个 \(i\) 时， \(dp_{x,y}\) 中满足 \(x=i\) 或 \(y=i\) 的有 \(O(n)\) 个，转移每个需要 \(O(n)\) 时间

扫描每个 \(i\) 时， \(dp_{x,y}\) 中满足 \(x=i\) 且 \(y=i\) 的有 \(O(1)\) 个，转移每个需要 \(O(n^2)\) 时间

因此复杂度为 \(O(n^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
const int N=110,P=1e9+7;

int n,k,J[N];
char s[N];
int G[N][N];

namespace pt1{
	void Solve(){
		int ans=1;
		rep(i,1,n) ans=1ll*ans*J[deg[i]]%P;
		printf("%d\n",ans);
	}
}

int deg[N];
int Calc1(int a,int b){
	static int dp[N];
	// calculate stategies that contain b->a
	memset(dp,0,sizeof dp);
	dp[b]=1;
	rep(i,1,n) {
		drep(j,n+1,i) if(dp[j]) {
			if(j==i) {
				if(i==a) dp[n+1]=(dp[n+1]+1ll*J[deg[i]-1]*dp[j])%P;
				else {
					rep(k,i+1,n) if(G[i][k]) dp[k]=(dp[k]+1ll*J[deg[i]-1]*dp[j])%P;
				}
			} else dp[j]=1ll*dp[j]*J[deg[i]]%P;
		}
	}
	return dp[n+1];
}

int Calc2(int a,int b,int c,int d){
	// calculate strategies that contain both b->a,d->c
	static int dp[N][N];
	memset(dp,0,sizeof dp),dp[b][d]=1;
	rep(i,1,n) {
		drep(x,n+1,i) drep(y,n+1,i) if(dp[x][y]) {
			int t=1ll*dp[x][y]*J[deg[i]-(x==i)-(y==i)]%P;
			if(x!=i && y!=i) { dp[x][y]=t; continue; }
			if(x!=i) {
				if(y==c) dp[x][n+1]+=t,Mod1(dp[x][n+1]);
				else rep(j,i+1,n) if(G[i][j]) dp[x][j]+=t,Mod1(dp[x][j]);
				continue;
			}
			if(y!=i) {
				if(x==a) dp[n+1][y]+=t,Mod1(dp[n+1][y]);
				else rep(j,i+1,n) if(G[i][j]) dp[j][y]+=t,Mod1(dp[j][y]);
				continue;
			}
			if(x==a) {
				if(y==c) dp[n+1][n+1]+=t,Mod1(dp[n+1][n+1]);
				else rep(j,i+1,n) if(G[i][j]) dp[n+1][j]+=t,Mod1(dp[n+1][j]);
				continue;
			}
			if(y==c) {
				rep(j,i+1,n) if(G[i][j]) dp[j][n+1]+=t,Mod1(dp[j][n+1]);
			} else {
				rep(j,i+1,n) if(G[i][j]) rep(k,i+1,n) if(G[i][k] && j!=k) dp[j][k]+=t,Mod1(dp[j][k]);
			}
		}
	}
	return dp[n+1][n+1];
}
namespace pt2{
	void Solve(){
		int a=-1,b=-1;
		rep(i,1,n) rep(j,1,i-1) if(G[i][j]) a=i,b=j;
		int ans=1;
		rep(i,1,n) ans=1ll*ans*J[deg[i]]%P;
		ans-=Calc1(a,b),Mod2(ans);
		printf("%d\n",ans);
	}
}

namespace pt3{
	void Solve(){
		int a=-1,b=-1,c=-1,d=-1;
		rep(i,1,n) rep(j,1,i-1) if(G[i][j]) {
			if(a==-1) a=i,b=j;
			else c=i,d=j;
		}
		int ans=1;
		rep(i,1,n) ans=1ll*ans*J[deg[i]]%P;
		ans-=Calc1(a,b),Mod2(ans);
		ans-=Calc1(c,d),Mod2(ans);
		ans+=Calc2(a,b,c,d),Mod1(ans);
		ans-=Calc2(c,b,a,d),Mod2(ans);
		printf("%d\n",ans);
	}
}

int main(){
	rep(i,*J=1,N-1) J[i]=1ll*J[i-1]*i%P;
	rep(_,1,rd()) {
		n=rd(),k=rd(),scanf("%s",s+1);
		rep(i,1,n) rep(j,1,n) scanf("%1d",G[i]+j);
		rep(i,1,n) {
			deg[i]=s[i]=='R';
			rep(j,1,n) deg[i]+=G[i][j];
		}
		if(k==0) pt1::Solve();
		else if(k==1) pt2::Solve();
		else pt3::Solve();
	}
}