cnyz's Blog

• https://darkbzoj.tk/problem/2873

题意：一个 $n$ 个节点的无向图，要求联通且只存在简单环，没有两环共点，求有多少种连边方式，对 $m$ 取模。

题目显然可以拆分为两个部分：

• 求出含 $i$ 个环的，$n$ 个点的图的个数。
• 求出 $n$ 个点组成 $i$ 个环的方案数。

显然第一个问题可以直接用 Cayley 定理解决，答案为 $n^{i-2}$。

考虑解决第二个问题：

设 $f_{i,j}$ 表示用 $i$ 个点组成 $j$ 个环的方案数，显然有：

$f_{i,j}=\sum^{i-j+1}_{k=1} f_{i-k,j-1}\times C^{k-1}_{i-1}\times s_k$

解释一下，我们枚举 $1$ 号点所在环的大小 $k$，显然从其他部分的方案为 $f_{i-k,j-1}$，而当前环的方案有 $C^{k-1}_{i-1}\times s_k$ 种，$s_k$ 表示在有多个环连接的情况下，有如下柿子：

$s_k=\frac{(k-1)!}{2}\times k$

其中 $\frac{(k-1)!}{2}$ 为普通圆排列公式，而 $\times k$ 为方向导致。

然而，本题还要特殊处理仅有一个环的情况，直接套圆排列公式即可。

时间复杂度 $O(n^3)$。

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=1;
int C[220][220],f[220][220],s[220];
int main() {
	scanf("%d %d",&n,&m);
	for(int i=0;i<=n;i++) {
		C[i][0]=1;
		for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%m;
	}
	s[1]=1,s[3]=3;
	for(int i=4;i<=n;i++) s[i]=1ll*s[i-1]*i%m;
	f[0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			for(int k=1;k<=i-j+1;k++)
				f[i][j]=(f[i][j]+1ll*f[i-k][j-1]*C[i-1][k-1]%m*s[k]%m)%m;
	for(int i=3;i<=n-1;i++) ans=(1ll*ans*i)%m;
	int tmp=1;
	for(int i=2;i<=n;i++) ans=(ans+1ll*f[n][i]*tmp%m)%m,tmp=1ll*tmp*n%m;
	printf("%d\n",ans%m);
}