「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是有交的

3.\(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)\),常数不算太大

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->amemset(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->cstatic 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);ans-=dp[n+1][n+1],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();}}