题解 \(by\;zj\varphi\)
一道概率与期望好题
对于一棵树，去掉根后所有子树就是一个森林，同理，一个森林加一个根就是一棵树
设 \(f_{i,j}\) 为有 \(i\) 个点的树，高度为 \(j\) 的期望，那么 \(f_{i,j}=g_{i-1,j-1}\) 其中 \(g_{i,j}\) 表示有 \(i\) 个点的森林深度为 \(j\) 的概率
一个森林也可以看成是一棵树加上一个森林
至于 \(g\)，\(g_{i,j}=\sum_{k=1}^{i}f_{k,j}g_{i-k,j}dp_{i,k}\) 其中 \(dp_{i,k}\) 就是一个有 \(i\) 个点的森林，有 \(k\) 个构成了一棵树
Code
#include<bits/stdc++.h>
#define ri register int
#define p(i) ++i
using namespace std;
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++
template<typename T>inline void read(T &x) {
ri f=1;x=0;register char ch=gc();
while(ch<'0'||ch>'9') {if (ch=='-') f=0;ch=gc();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
x=f?x:-x;
}
}
using IO::read;
namespace nanfeng{
// #define int long long
#define FI FILE *IN
#define FO FILE *OUT
template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}
template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}
typedef long long ll;
static const int N=220;
int dp[N][N],f[N][N],g[N][N],inv[N],n,p,ans;
inline int fpow(int x,int y) {
ri res=1;
while(y) {
if (y&1) res=(ll)res*(ll)x%p;
x=(ll)x*x%p;y>>=1;
}
return res;
}
inline int main() {
// FI=freopen("nanfeng.in","r",stdin);
// FO=freopen("nanfeng.out","w",stdout);
read(n),read(p);
for (ri i(2);i<=n;p(i)) inv[i]=fpow(i,p-2);
dp[1][0]=dp[1][1]=1;
for (ri i(2);i<=n;p(i)) {
for (ri j(1);j<=i;p(j)) {
dp[i][j]=(ll)dp[i-1][j-1]*(j-1)%p*inv[i]%p+(ll)dp[i-1][j]*(i-j)%p*inv[i]%p;
dp[i][j]%=p;
}
}
for (ri i(0);i<=n;p(i)) f[0][i]=g[0][i]=1;
for (ri i(1);i<=n;p(i))
for (ri j(i-1);j<n;p(j)) f[i][j]=g[i][j]=1;
for (ri i(2);i<=n;p(i)) {
for (ri j(0);j<i-1;p(j)) {
if (j) f[i][j]=g[i-1][j-1];
for (ri k(1);k<=i;p(k)) {
g[i][j]+=(ll)f[k][j]*g[i-k][j]%p*dp[i][k]%p;
g[i][j]%=p;
}
}
}
for (ri i(1);i<n;p(i)) ans+=(ll)i*((f[n][i]-f[n][i-1]+p)%p)%p,ans%=p;
printf("%d\n",ans);
return 0;
}
}
int main() {return nanfeng::main();}