[HAOI2018]苹果树 - A-Failure的博客

题目

题目描述

小C在自己家的花园里种了一棵苹果树，树上每个结点都有恰好两个分支。经过细心的观察，小C发现每一天这棵树都会生长出一个新的结点。

第一天的时候, 果树会长出一个根结点，以后每一天，果树会随机选择一个当前树中没有长出过结点的分支，然后在这个分支上长出一个新结点，新结点与分支所属的结点之间连接上一条边。

小C定义一棵果树的不便度为树上两两结点之间的距离之和，两个结点之间的距离定义为从一个点走到另一个点的路径经过的边数。

现在他非常好奇，如果 $N$ 天之后小G来他家摘苹果，这个不便度的期望 $E$ 是多少。但是小C讨厌分数,，所以他只想知道 $E \times N!$ 对 $P$ 取模的结果，可以证明这是一个整数。

输入格式

一行两个整数$N, P$。

输出格式

输出一个整数表示答案。

样例

样例输入1

3 610745795

样例输出1

样例输入2

305 1000000007

样例输出2

865018107

数据范围与提示

对于 $20\%$ 的数据，$N \le 10$；

对于 $50\%$ 的数据，$N \le 500$；

对于另外 $20\%$ 的数据，$P = 10^9 + 7$

对于 $100\%$ 的数据，$N \le 2000, P \le 10^9 + 7$。

题解

还是思维不行啊……

看到统计两两之间距离和，首先想到统计每条边的贡献，即一个端点代表的子树大小乘其他点的个数

$n$只有$2000$，所以可以枚举端点和子树大小，假设现在枚举到点$i$，子树大小为$a$，$i$子树里的点肯定编号大于$i$，所以有$C_{n-i}^{a-1}$种选择，总的方案数就是$a!\times C_{n-i}^{a-1}$

再考虑子树外的贡献，可以看成已经建出一颗$i$个点的树，这里的方案数为$i!$，然后剩下的$n-i-a+1$个点往上插，$n$个点能往上插的节点个数为$n+1$，因为$i$节点已经确定下来了不能往上插（$i$肯定为叶子节点），所以插第一个点的方案数为$i+1-2$，第二个点可以往第一个点上插，方案数为$i+2-2$，……

以此类推，总方案数为$i!(i-1)i(i+1)…(n-a-1)=\frac{i!(n-a-1)!}{(i-2)!}=i(i-1)(n-a-1)!$

所以题目要求为$\sum_{i=1}^{n}\sum_{a=1}^{n-i+1}(a!\times C_{n-i}^{a-1}\times a)\times (i(i-1)(n-a-1)!\times (n-a))$

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int N=2e3+5;
int n,P,ans;
int fac[N];
int C[N][N];
int main()
{
	scanf("%d%d",&n,&P),fac[0]=1;
	for(int i=1;i<=n;++i)
	  fac[i]=1ll*fac[i-1]*i%P;
	for(int i=0;i<=n;++i)
	  C[i][0]=1;
	for(int i=1;i<=n;++i)
	  for(int j=1;j<=i;++j)
	    C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
	for(int i=1;i<=n;++i)
	  for(int a=1;a<=n-i+1;++a)
	    (ans+=1ll*fac[a]*C[n-i][a-1]%P*a%P*i%P*(i-1)%P*fac[n-a-1]%P*(n-a)%P)%=P;
	return printf("%d",ans),0;
}

题目