链接

<h2>题目描述</h2>

随机一棵以 $1$ 为根，且节点编号满足小根堆性质的树的期望最大深度。
$n \leq 200$

<h2>题解</h2>

这个题我考试的时候连 $n \leq 20$ 都不会..还是自己太菜了。

一开始的一个想法是记 $f_{i,j}$ 表示前 $i$ 个点深度为 $j$ 的树的个数，然后发现不太能转移需要记录最后一层的节点个数。。然后还要记录前面层的所以复杂度就炸了。
然后我们考虑放宽限制，对森林计数，并且我们不妨做一步容斥：设 $f_{i,j}$ 表示 $i$ 个节点，最大深度 $\leq j$ 的树的个数，$g_{i,j}$ 表示 $i$ 个节点，最大深度为 $j$ 的森林的个数。
我们首先预处理出 $dp_{i,j}$ 表示从 $i$ 个点中选出 $j$ 个点组成一棵树的概率，转移
$$dp_{i,j} = dp_{i-1,j-1} * \frac{j-1}{i} + dp_{i-1,j} * \frac{i-j}{i}$$
用 $g$ 转移 $f$ 的时候我们可以考虑变出一个根把这些树都接到根上，有 $f_{i,j} = g_{i-1,j-1}$
用 $f$ 转移 $g$ 其实是一个经典套路：我们枚举编号最小的点所在的树的大小，那么有转移
$$g_{i,j} = \sum_{k=1}^i f_{k,j} * dp_{i,k} * g_{i-k,j}$$
其中 $f_{k,j} * dp_{i,k}$ 是计算了拿出 $k$ 个点组成一棵树的概率，所以我们不需要关系组合计数那一堆东西了（有时候把概率引入到状态就是好用）
答案统计就不说了。

<h2>反思</h2>

对于树的计数：如果对度数进行限制就对 prufer 序列进行计数，对深度进行限制可以考虑利用森林辅助转移。
其实树是点的集合，森林是树的集合，如果我们固定 $j$，那么树的生成函数 $F$ 和森林的生成函数 $G$ 满足 $e^F = G$（虽然这个题目只能提高复杂度）
并且考试一定要把所有性质读完，要不然会导致漏掉性质把会做的题不会做
概率问题计数不可做可以考虑直接设概率为状态（就是不知道会不会有计数转概率最后再乘回去的）

<h2>题解</h2>

/*
 * Author: RainAir
 * Time: 2019-11-01 14:54:40
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 200+5;
int n,ha;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1llresa%ha;
        a = 1llaa%ha;
        n >>= 1;
    }
    return res;
}

int getf(int,int);
int getg(int,int);

int fMAXN,gMAXN,dpMAXN;

inline int getf(int i,int j){
    if(fi != -1) return fi;
    return fi = getg(i-1,j-1);
}

inline int getg(int i,int j){
    if(j < 0) return 0;
    if(!i) return 1;
    if(!j) return 0;
    if(gi != -1) return gi;
    int &res = gi;res = 0;
    FOR(k,1,i){
        (res += 1llgetg(i-k,j)getf(k,j)%ha*dpi%ha) %= ha;
    }
    return res;
}

int t[MAXN];

int main(){
//    freopen("toy.in","r",stdin);
//    freopen("toy.out","w",stdout);
    scanf("%d%d",&n,&ha);
    CLR(f,-1);CLR(g,-1);
    dp1 = 1;
    FOR(i,2,n){
        FOR(j,1,i){
            int inv = qpow(i);
            dpi = (1lldpi-1(j-1)%hainv%ha+1lldpi-1(i-j)%hainv%ha)%ha;
        }
    }
    FOR(i,1,n) t[i] = getf(n,i);
    ROF(i,n,1) t[i] = (t[i]+ha-t[i-1])%ha;
    int ans = 0;
    FOR(i,2,n) (ans += 1llt[i](i-1)%ha) %= ha;
    printf("%lldn",1ll*ans%ha);
    return 0;
}