自动搬运

查看原文

来自洛谷，原作者为

	Amidst 生若直木，不语斧凿。

搬运于2025-08-24 22:30:45，当前版本为作者最后更新于2025-04-14 11:03:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路

很容易想到欧拉回路。

我们考虑增加一个超级源点 $C$，将 $C$ 与所有起点之间连一条有向边，再增加一个超级汇点 $D$，将所有终点与 $D$ 之间连一条有向边，$D$ 和 $C$ 之间再连边，就变成了一个有向图欧拉回路计数问题。

于是考虑 BEST 定理。

BEST 定理

设 $G$ 为有向欧拉图，$k$ 为任意顶点，则 $G$ 的不同欧拉回路个数

$$\operatorname{euc}(G)=t^{\mathrm{in}}(G,k)\prod\limits_{v\in V}(\deg(v)-1)! $$

BEST 定理表明，对于 $\forall k,k'\in V_G$，都有 $t^{\mathrm{in}}(G,k)=t^{\mathrm{in}}(G,k')$。

证明

考虑图 $G$ 的任意一棵内向树，对于每个节点 $u$，我们给以 $u$ 为起点的所有不在内向树上的 $\deg(u)-1$ 条出边一个顺序，称这个根向树及这个出边的排列顺序为一个组合。

于是我们只需要证明组合和欧拉回路一一对应。

考虑从根节点开始，每到达一个节点，若不在内向树上的出边都被走过了，就沿着根向树上的边走向其父亲，否则就按照出边的排列顺序走向下一个节点。

注意到这样只会经过每个节点至多一次，现在证明这样会经过且仅经过每个节点一次。

不妨设到达节点 $u$ 后无法移动，考虑分类讨论。

若 $u$ 不是根节点，我们经过 $u$ 时会经过其一条入边和一条出边，而无法移动说明只经过了 $u$ 的一条入边，说明 $\deg^{\mathrm{in}}(u)=\deg^{\mathrm{out}}(u)+1$，与 $G$ 为欧拉图矛盾。

这样我们就证明了这种方案一定会形成一个欧拉回路。

现在我们证明了一个组合对应一个欧拉回路，接下来考虑证明一个欧拉回路对应一个组合。

记 $e_u$ 为 $u$ 最后访问的入边，下面证明所有 $e_u$ 构成一棵内向树。

不妨设 $e_u$ 构成的图中有环，首先根节点必然不会出现在环上。现在环上找出任意一个节点 $u$，容易发现 $u$ 沿着环的方向可以再次回到 $u$。由于原图是欧拉图，$\deg^{\mathrm{in}}(u)=\deg^{\mathrm{out}}(u)$，而 $u$ 在环上回到 $u$ 会导致 $\deg^{\mathrm{in}}(u)=\deg^{\mathrm{out}}(u)+1$，矛盾，故所有 $e_u$ 构成树。

于是一个组合和一个欧拉回路一一对应。

---

由上文我们知道

$$\operatorname{euc}(G)=t^{\mathrm{in}}(G,k)\prod\limits_{v\in V}(\deg(v)-1)! $$

在本题中即为

$$\operatorname{euc}(G)=t^{\mathrm{in}}(G,S_b)\deg(S_b)(\deg (S_b)-1)!(\deg(S_e)-1)!\prod\limits_{i=1}^{n}(\deg(i)-1)! $$

其中 $S_b$ 是超级源点，$S_e$ 是超级汇点。

但是仅仅套用 BEST 定理还不够。

而本题中由于我们建立了超级源点和超级汇点，与这两个点相连的边的决策带来的额外方案数不能被算入答案中，由排列的基本知识可以得到这样会令答案额外乘

$$\deg(S_b)!\deg(S_e)!$$

注意 $e=(S_b,S_e)$ 不计入两点度数。

于是有

$$\begin{aligned}ans(G)&=\frac{t^{\mathrm{in}}(G,S_b)\deg(S_b)(\deg (S_b)-1)!(\deg(S_e)-1)!\prod\limits_{i=1}^{n}(\deg(i)-1)!}{\deg(S_b)!\deg(S_e)!}\\&=\frac{t^{\mathrm{in}}(G,S_b)\prod\limits_{i=1}^{n}(\deg(i)-1)!}{\deg(S_e)}\end{aligned} $$

显然，$\deg(S_e)$ 即为给定的字符串中 S 的个数。

注意到题目描述中的一句话：每条边使用恰好一次，所以要删除孤立点后再计算。

代码

#include <bits/stdc++.h>
//#include <bits/extc++.h>
#define int long long
#define mod (int)(1e9+7)
#define __MULTITEST__
//#undef __MULTITEST__
using namespace std;
//using namespace __gnu_cxx;
//using namespace __gnu_pbds;
int a[105][105];
string s[105];
int ind[105],oud[105],iid[105];
int cntiid;
int quick_pow(int a,int b,int p)
{
	int ret=1;
	while(b)
	{
		if(b&1)
			ret=ret*a%p;
		a=a*a%p;
		b>>=1;
	}
	return ret;
}
void updeg(int u,int v)
{
	ind[v]++;
	oud[u]++;
}
void upcon(int u,int v)
{
	u=iid[u];
	v=iid[v];
	a[u][v]=(a[u][v]+mod-1)%mod;
	a[v][v]=(a[v][v]+1)%mod;
}
int det(int n)
{
	int ans=1,f=1;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
		{
			while(a[i][i])
			{
				int tmp=a[j][i]/a[i][i];
				for(int k=i;k<=n;k++)
					a[j][k]=(a[j][k]-a[i][k]*tmp%mod+mod)%mod;
				for(int k=1;k<=n;k++)
					swap(a[i][k],a[j][k]);
				f=-f;
			}
			for(int k=1;k<=n;k++)
				swap(a[i][k],a[j][k]);
			f=-f; 
		}
	for(int i=1;i<=n;i++)
		if(a[i][i])
			ans=ans*a[i][i]%mod;
	return (ans*f%mod+mod)%mod; 
}
int n,k,ans;
int fac[305];
signed main()
{
	fac[0]=1;
	for(int i=1;i<=300;i++)
		fac[i]=fac[i-1]*i%mod; 
	#ifdef __MULTITEST__
	signed T;
	scanf("%d",&T);
	while(T--)
	{
	#endif
		memset(ind,0,sizeof ind);
		memset(oud,0,sizeof oud);
		memset(iid,0,sizeof iid);
		memset(a,0,sizeof a);
		cntiid=0;
		scanf("%lld%lld",&n,&k);
		string st;
		cin>>st;
		st='#'+st;
		for(int i=1;i<=n;i++)
		{
			if(st[i]=='S')
			{
				updeg(n+1,i);
				updeg(n+2,n+1);
			}
			if(st[i]=='R')
				updeg(i,n+2);
		}
		for(int i=1;i<=n;i++)
		{
			cin>>s[i];
			s[i]='#'+s[i];
			for(int j=1;j<=n;j++)
				if(s[i][j]=='1')
					updeg(i,j);
		}
		for(int i=1;i<=n+2;i++)
			if(ind[i]!=oud[i])
			{
				printf("0\n");
				goto label;
			}
		for(int i=1;i<=n+2;i++)
			if(i!=n+1&&ind[i])
				iid[i]=++cntiid;
		for(int i=1;i<=n;i++)
		{
			if(st[i]=='S')
			{
				upcon(n+1,i);
				upcon(n+2,n+1);
			}
			if(st[i]=='R')
				upcon(i,n+2);
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(s[i][j]=='1')
					upcon(i,j);
		ans=det(cntiid);
		for(int i=1;i<=n;i++)
			if(oud[i])
				ans=(ans*fac[oud[i]-1]%mod+mod)%mod;
		ans=ans*quick_pow(oud[n+1],mod-2,mod)%mod;
		printf("%lld\n",ans);
		label:
			;
	#ifdef __MULTITEST__
	}
	#endif
	return 0;
}