[HAOI2018]苹果树

2024-04-05 14:40:00

题目描述

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

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

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

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

输入输出格式

输入格式：

从标准输入中读入数据. 一行两个整数 NN, PP .

输出格式：

输出到标准输出中. 输出一个整数表示答案．

输入输出样例

输入样例#1：

3 610745795

输出样例#1：

24

输入样例#2：

305 1000000007

输出样例#2：

865018107

题解

挺难的一道计数题,对着题解理解半天才大致搞懂
首先观察题目可以发现:每棵二叉树对应了唯一的中序遍历
所以当我们要放第\(i\)个点的时候就有\(i\)种方案了
计算点对间的距离肥肠困难,所以我们只考虑每条边对答案的贡献
显然一条边\((u,v)\)的贡献就是\(size[v]*(n-size[v])\),也就是一条边的一端的子树中走到另一端的子树中的方案数
有了每条边对一种方案的贡献,我们就可以考虑去计算每条边的方案数了
我们发现每条边出现不同的贡献的原因就是这条边的一端的子树大小不同
所以就可以考虑枚举这条边的一端的子树的大小来计算每条边的贡献
那么现在只需要解决有多少种方案满足点\(i\)的子树大小为\(sz\)即可
考虑将子树内和子树外的方案数分开计算

先考虑\(i\)的子树内的情况:

如果没有标号的话点i就有\(sz!\)种不同的子树
显然点\(i\)的子树内点的标号一定比\(i\)要大,且\(i\)这个标号一定要选
所以可选取的标号的方案数就是\(C(n - i , sz)\)
所以子树这一部分的方案数是\(C(n - i , sz) * sz!\)

再考虑\(i\)的子树外的情况

我们可以这么考虑,由于我们已经弄了一个\(i\)及\(i\)的子树了
所以我们就把点\(i\)及其子树想成一个大的点且这个点的左右儿子都不能选
这样我们要处理的点的数量就是\(n - sz + 1\)
由于子树内已经选完\(sz-1\)个点了,所以剩下的\(n - sz + 1\)个点是确定的
前\(i\)个点没有限制,所以方案数就是\(i!\)
然后对于后面的某一点\(i+k(i + k <= n - sz + 1)\),由于点\(i\)的左右子树都不能选了,所以方案数就是\(i + k - 2\)
这样一来后面的点的方案数就是\(\prod_{k=1}^{i+k<=n-sz+1}{i+k-2}\)
所以子树外这一部分的方案数就是\(i!\prod_{k=1}^{i+k<=n-sz+1}{i+k-2}=(i-1)*i*(n-sz-1)!\)

所以总的方案数就是\(C(n - i , sz) * sz!*(i-1)*i*(n-sz-1)!\)
然后再乘上这条边的贡献\(sz*(n-sz)\)就是答案了

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
const int M = 2005 ;
using namespace std ;

int n , mod , ans , C[M][M] , fac[M] ;

int main() {
    scanf("%d%d",&n,&mod) ;
    C[0][0] = 1 ;
    for(int i = 1 ; i <= n ; i ++) {
        C[i][0] = 1 ;
        for(int j = 1 ; j <= i ; j ++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod ;
    }
    fac[0] = 1 ;
    for(int i = 1 ; i <= n ; i ++) fac[i] = 1LL * fac[i - 1] * i % mod ;
    for(int i = 2 ; i <= n ; i ++)
        for(int sz = 1 ; sz <= n - i + 1 ; sz ++)
            ans = (ans + 1LL * sz * (n - sz) % mod * C[n - i][sz - 1] % mod * fac[sz] % mod * (i - 1) % mod * i % mod * fac[n - sz - 1] % mod) % mod ;
    printf("%d\n",ans) ;
    return 0 ;
}

码农公寓