[HAOI2018]苹果树

题目大意：

一个(n(nle2000))个点的二叉树，初始时只有一个根结点(1)。按顺序加入(2sim n)的结点。每次随机一个未拓展的分支加入一个新的结点。求最后树上所有点对之间的距离之和的期望(E imes n!)对(p(ple10^9+7))取模的结果。

思路：

对于(n)个点的二叉树，加入点(1)时有(1)个分支可以加，加入点(2)时有(2)个分支可以加，以此类推，加入点(n)时有(n)个分支可以加。每加入一个点会在覆盖掉原来一个分支的基础上增加两个分支。因此若考虑结点编号的不同，(n)个结点的二叉树有(n!)种形态。

将问题转化为加入一条边后，每条边对答案的贡献。若树的形态确定，考虑经过一条边的点对，若在树上去掉这条边，将树分为大小分别为(j)和(n-j)的两个连通块，则这条边对答案有(n(n-j))的贡献。

然而，现在树的形态是不确定的。对于现在加入第(i-1)条边，我们不妨枚举边下端的子树大小(j)。显然若在子树内结点编号确定的情况下，共有(j!)种子树。子树的根结点一定是(i)，从(n-i)个结点中选择(j-1)个作为子树中的结点，总共有(inom{n-i}{j-1})种方法。

对于编号为(1sim i)的点，共有(i!)种生成方式。对于剩下的(n-j-i+1)个结点，由于不能让它们加到(i)的子树中，因此他们分别有((i-1),i,ldots,(n-j-1))种方法可以加。也就是说，算上前面(i!)个点，子树外共有((n-j-1)!cdot icdot(i-1))种方法。

答案即为(sum_{i=2}^nsum_{j=1}^{n-i+1}j!cdotinom{n-i}{j-1}cdot jcdot(n-j)!cdot icdot(i-1))。

时间复杂度(mathcal O(n^2))。

源代码：

#include<cstdio>
#include<cctype>
typedef long long int64;
inline int getint() {
	register char ch;
	while(!isdigit(ch=getchar()));
	register int x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return x;
}
const int N=2001;
int n,mod,fac[N],c[N][N];
int main() {
	n=getint(),mod=getint();
	for(register int i=c[0][0]=1;i<=n;i++) {
		for(register int j=c[i][0]=1;j<=i;j++) {
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
		}
	}
	for(register int i=fac[0]=1;i<=n;i++) {
		fac[i]=(int64)fac[i-1]*i%mod;
	}
	int ans=0;
	for(register int i=2;i<=n;i++) {
		for(register int j=1;j<=n-i+1;j++) {
			(ans+=(int64)j*fac[j]%mod*c[n-i][j-1]%mod*fac[n-j]%mod*i*(i-1)%mod)%=mod;
		}
	}
	printf("%d
",ans);
	return 0;
}