OI - Unicyclic Graph Counting(Atcoder)

为什么洛谷对 Atcoder 的 RemoteJudge 挂了啊 :(

---

# 题面

点击展开/折叠题意

n 个点的有标号基环树，第 i 个点的度数为 $d_i$，求满足条件的基环树的个数对 $10^9+7$ 取模的结果。

---

# 解析

关于图的计数，尤其是“树”的计数，想到的比较多的就是 prufer 和 Matrix-Tree，这道题便是用 prufer。

但是 prufer 本身只能解决树的计数。

基环树的特点就是把仅有的一个环缩点后变成了一棵树。于是可以考虑计算缩点后对应的树的方案——

假设环的点集为 $S$：

1. 构成这个环的方案数即是圆排列 $\frac{(|S|-1)!}2$；
2. 缩点后环的度数为 $\sum\limits_{i\in S}(d_i-2)$（即每个点除了和环上相邻两个点连边以外的边）、总点数为 $(n-|S|+1)$，则根据 prufer数列 可重排的性质，缩点得到的树的方案数为 $$\frac{(n-|S|-1)!}{(\sum\limits_{i\in S}(d_i-2)-1)!\prod\limits_{i\not\in S}(d_i-1)!}$$
3. 虽然环缩成了一个点 x，但是连到 x 上的边实际上有区别，环上每个点的出边数量为 $d_i-2$，则根据可重排，连到环上的边的方案数为 $$\frac{(\sum_{i\in S}(d_i-2))!}{\prod_{i\in S}(d_i-2)!}$$

综上，选的点集为 $S$ 对应的方案数为：

$$\frac{(|S|-1)!}2\times \frac{(n-|S|-1)!}{(\sum\limits_{i\in S}(d_i-2)-1)!\prod\limits_{i\not\in S}(d_i-1)!}\times \frac{(\sum_{i\in S}(d_i-2))!}{\prod_{i\in S}(d_i-2)!}$$

化简一下

$$\frac{(|S|-1)!}2\times \frac{(\sum_{i\in S}(d_i-2))!}{(\sum_{i\in S}(d_i-2)-1)!}\times\frac{(n-|S|-1)!}{\prod_{i\not\in S}{(d_i-1)!}\prod_{i\in S}(d_i-2)!}$$

继续化简：

$$\frac{(|S|-1)!(n-|S|-1)!}2\times\frac{\prod_{i\in S}{(d_i-1)}}{\prod_i(d_i-1)!}\times\left(\sum_{i\in S}{d_i-2|S|}\right)$$

发现我们需要计算的是 $\prod_{i\in S}(d_i-1)$ 和 $\sum_{i\in S}d_i$，于是定义DP状态：f[i][j][k] 表示前 i 个点，有 j 个在 S 中，此时 $\sum_{i\in S}d_i=k$，对应的所有方案的 $\prod_{i\in S}(d_i-1)$ 之和。

转移 $O(1)$，状态 $O(n^3)$，总复杂度 $O(n^3)$，空间复杂度可以滚掉第一维，即 $O(n^2)$。

---

# 源代码

/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MOD=1e9+7,N=610,INV2=500000004;

#define cs const int &
inline int Add(cs a,cs b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(cs a,cs b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(cs a,cs b){return 1ll*a*b%MOD;}
inline int Pow(int a,int b){int r=1;while(b){if(b&1)r=Mul(r,a);a=Mul(a,a),b>>=1;}return r;}

int n;
int d[N],fac[N],ifac[N];
int f[2][N][N];

int main(){
	fac[0]=1;for(int i=1;i<N;i++) fac[i]=Mul(fac[i-1],i);
	ifac[N-1]=Pow(fac[N-1],MOD-2);for(int i=N-2;i>=0;i--) ifac[i]=Mul(ifac[i+1],i+1);
	scanf("%d",&n);
	int cnt2=0,all=0;
	for(int i=1;i<=n;i++) scanf("%d",&d[i]),cnt2+=d[i]==2,all+=d[i];
	if(cnt2==n){printf("%d\n",Mul(fac[n-1],INV2));return 0;}
	f[0][0][0]=1;
	for(int i=1,I=1;i<=n;i++,I^=1)
		for(int j=0;j<=i;j++)
			for(int k=0;k<=all;k++){
				f[I][j][k]=f[I^1][j][k];
				if(j && d[i]>=2 && k>=d[i])
					f[I][j][k]=Add(f[I][j][k],Mul(f[I^1][j-1][k-d[i]],d[i]-1));
			}
	int ans=0,pod=1;
	for(int i=1;i<=n;i++) pod=Mul(pod,ifac[d[i]-1]);
	for(int S=3;S<n;S++)
		for(int de=2*S;de<=all;de++){
			int mul=Mul(fac[S-1],fac[n-S-1]);
			mul=Mul(mul,Mul(INV2,pod));
			mul=Mul(mul,Sub(de,2*S));
			// printf("[%d][%d]=%d\n",S,de,f[n&1][S][de]);
			ans=Add(ans,Mul(mul,f[n&1][S][de]));
		}
	printf("%d\n",ans);
	return 0;
}

---

THE END

Thanks for reading!

$$\begin{split} “\ &添酒回灯\\ &转轴拨弦诉尽一生衷肠\\ &后街的夏风\\ &巷中的熙攘\\ &这城\ 华灯初上\ ”\\ ——&\text{《三杯空城》By 洛天依/COP} \end{split}$$

> Linked 三杯空城-网易云