「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 ightarrow a ightarrow b ightarrow R_1 (a>b))
则断掉后的路径变成(S_1 ightarrow a)，(b ightarrow R)
不妨将在(a)上额外添加一个(R)，在(b)上额外添加一个(S)
此时，新的问题又只包含((u,v)(u<v))，同(K=0)求解
理想情况下，新问题中的所有方案均可以通过将(a,b)相接还原
但是显然如果最终方案上(b ightarrow a)相接就会成环
所以需要额外(dp)出包含(b ightarrow a)的非法方案
考虑用类似(K=0)的办法，我们扫描每个(i)将(S)向后推
令(dp_i)表示当前(dp)的路径最后一个点是(i)的方案数
我们希望结束点是(a)，开始点是(b)
此时依次推过去(i)，此时只有(dp_{j},jge i)的情况是合法的
考虑(j=i)时，需要为(j)找一个归宿(k)，或者判定(j=a)时结束路径
此时，相当于在原图上使(outd_i)减少了(1)
得到转移(dp_kleftarrow dp_jcdot (outd_i-1)!)
当(j>i)时，不需要考虑(j)的变化
得到转移(dp_jleftarrow dp_jcdot outd_i!)
(K=2)
有了(K=1)的铺垫，想必这里十分简单
设反边为((a,b),(c,d))，显然加入两组(S,R)
考虑新图上什么样的情况是不合法的
1.(b ightarrow a)
2.(d ightarrow c)
注意1,2是有交的
3.(b ightarrow c ightarrow d ightarrow 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
",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
",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
",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();
}
}