Description：

一棵二叉树，刚开始有一个点，然后每次在所有可以插入一个新点的地方等概率选一个插入，求最后两两节点之间的距离之和的期望乘 $N!$ 的结果。

$1\leqslant n\leqslant 2000$

Solution：

刚开始觉得是一步一步 $DP$ 发现不可做。

首先加入第 $i$ 个点的时候有 $i$ 种选法，也就是说最后有 $N!$ 种不同的二叉树，换个角度理解可以看成是每一种中序遍历都对应同一种树，直接计算不好算，我们可以对于每一条边算贡献，对于 $(i,fa[i])$ 这条边，贡献显然是 $siz[i]\times (n-siz[i])$ ，那么我们可以先枚举 $i$ ，然后再枚举 $siz[i]$ ，于是现在我们的问题变成了求有多少种树 $i$ 的子树有 $siz[i]$ 个点，里面的是 $siz[i]!\binom{n-i}{siz[i]-1}$ ，外面的在 $i$ 之前有 $i!$ 种方案，在 $i$ 的后面除了确定的其他的都不能放在 $i$ 的子树中，方案数就是 $(i-1)i(i+1)\cdots (n-siz[i]-1)$ 最后就是 $i(i-1)(n-siz[i]-1)$ ，于是答案就是： $$ ans=\sum_{i=2}^n\sum_{siz=1}^{n-i+1}siz!\binom{n-i}{siz-1}i(i-1)(n-siz-1)!siz(n-siz) $$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,p;

#define MAXN 2010

int C[MAXN][MAXN];

int Add(int a,int b){return (a + b >= p ? a + b - p : a + b);}

int fac[MAXN];

int main()

{

	scanf("%d%d",&n,&p);

	C[0][0] = 1;

	fac[0] = 1;

	for(int i = 1;i <= n;++i)

	{

		fac[i] = 1ll * fac[i - 1] * i % p;

		C[i][0] = 1;

		for(int j = 1;j <= i;++j)C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % p;

	}

	int ans = 0;

	for(int i = 2;i <= n;++i)

	{

		for(int siz = 1;siz <= n - i + 1;++siz)

		{

			ans = Add(ans,1ll * fac[siz] * C[n - i][siz - 1] % p * i % p * (i - 1) % p * fac[n - siz - 1] % p * siz % p * (n - siz) % p);

		}

	}

	cout << ans << endl;

	return 0;

}