bzoj1211-树的计数

题意

给出 \(n\) 和长度为 \(n\) 的数列 \(d\) 表示每个点的度数，问有多少颗满足要求的树。

分析

这题是prufer编码的应用。

prufer编码是对一个带标号无根树的刻画，生成方式是：对于一棵树，每次找到度数为1的编号最小的节点，把与这个节点相邻的那个节点加在生成数列后面，删除这个节点；进行这个过程直到树只剩下两个点。这样我们就生成了这棵树的prufer数列，长度为 \(n-2\) 。

反过来，一个prufer编码唯一对应一棵树，因为我们可以用prufer编码唯一对应回一棵树，因此构成双射。解码方法如下：对于 \(i=n-2\cdots 1\) ，找出在prufer序列中后 \(i\) 个数中没有出现过的而且没有用过的最小数 \(x\)，加边 \((x,a_i)\) ，把 \(x\) 标记为用过。最后剩下的一个数直接连在最后一位上即可。很明显每次我们都能唯一确定这个数，因此可以唯一地连边。

这题的答案是

\[\frac{(n-2)!}{\prod _{i=1}^n(d_i-1)!}
\]

原因是每个点的度数为 \(d_i\) 就代表它在prufer数列中出现了 \(d_i-1\) 次，所以我们把这些数对应到\(1\cdots n-2\)上，用全排列除去对应位置的全排列，即把那些数看成了相同的。

这题中间计算过程会超long long，所以要记录一下质因数什么的。还有 \(n=1\) 的情况特判。

代码

#include<bits/stdc++.h>

using namespace std;

inline int read() {

	int x=0,f=1;

	char c=getchar();

	for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;

	for (;isdigit(c);c=getchar()) x=x*10+c-'0';

	return x*f;

}

const int maxn=151;

int p[maxn],ps=0,from[maxn];

bool np[maxn];

int f[maxn][maxn],ans[maxn];

int n,d[maxn],sum=0;

int main() {

#ifndef ONLINE_JUDGE

	freopen("test.in","r",stdin);

#endif

	for (int i=2;i<maxn;++i) {

		if (!np[i]) p[++ps]=i,from[i]=1;

		for (int j=1;j<=ps && i*p[j]<maxn;++j) {

			np[i*p[j]]=true;

			from[i*p[j]]=i;

			if (i%p[j]==0) break;

		}

	}

	for (int i=2;i<maxn;++i) for (int j=i;j>1;j=from[j]) ++f[i][j/from[j]];

	n=read();

	for (int i=1;i<=n;++i) sum+=(d[i]=read()-1);

	if (n==1 && d[1]==-1) puts("1"),exit(0);

	for (int i=1;i<=n;++i) if (d[i]<0) puts("0"),exit(0);

	if (sum!=n-2) puts("0"),exit(0);

	for (int i=2;i<maxn;++i) ans[i]+=f[n-2][i];

	for (int i=1;i<=n;++i) for (int j=2;j<maxn;++j) ans[j]-=f[d[i]][j];

	long long the=1;

	for (int i=2;i<maxn;++i) for (int k=1;k<=ans[i];++k) the*=i;

	printf("%lld\n",the);

	return 0;

}