题目描述：
这个故事发生在很久以前，在 IcePrincess_1968 和 IcePrince_1968 都还在上幼儿园的时候。
IcePrince_1968 最近迷上了一种玩具，这种玩具中有两种零件：圆球和棍子。棍子的两头可以插在两个圆球上的各一个空洞中，从而将两个圆球连接起来。为了保证玩具的娱乐性，任意一个圆球上的空洞个数总是多于玩具套装中的棍子数。你可以认为圆球是没有体积的，所有棍子的长度均为 1。
IcePrince_1968 喜欢这样玩这种玩具：他先摸出玩具袋里的一个圆球放在地上，然后重复下面的操作 n-1 次：每次从袋中取出一个圆球和一根棍子，然后等概率的从地上的圆球中选择一个，将该圆球和选择的圆球用棍子连起来，使得新的圆球在选中圆球的正上方。
IcePrince_1968 对自己搭出的艺术品很满意，便决定把这个物品送给 IcePrincess_1968 作为生日礼物。然而生日礼物是需要包装的，因为默认圆球没有体积，所以 IcePrince_1968 不用考虑包装盒的长和宽，但是包装盒的高是需要确定的，这里我们假设 IcePrince_1968 是一个非常节俭的孩子，所以包装盒的高总是等于艺术品的高度。IcePrince_1968 想知道自己需要的包装盒的高的期望对质数 p 取模后的值，但他还在上幼儿园，怎么会算呢，于是就请你来帮助他。
输入：
输入数据仅一行，包含两个正整数 n,p，表示最终的艺术品中圆球的个数和模数 p。
输出：
输入文件仅一行，一个正整数，表示包装盒的高的期望对质数 p 取模后的值。
数据范围：
对于 30%的数据，满足 n<=10,p<=1,000,007；
对于 50%的数据，满足 n<=20；
对于 70%的数据，满足 n<=50；
对于 100%的数据，满足 n<=200,p<=1,000,000,007,p 是质数。
算法标签：期望DP
（一下思路几乎都摘自，出题人的题解，因为本蒟蒻实在是不太会写期望dp....考场连题都没理解透哭了...）
思路：
预处理dp[i][j]表示i个点的森林，有j个点在第一棵树的概率，转移考虑第i个点是否在第一棵树中，我们有状态转移方程：
dp[i][j] = dp[i − 1][j − 1] ∗ (j − 1) ∗ inv[i] + dp[i − 1][j] ∗ (i − j) ∗ inv[i]
考虑修改算法三中状态的含义，令f[i][j]表示有i个点的树，深度不超过j的概率，g[i][j]表示有i个点的森林，深度不超过j的概率，f[i][j]直接从g[i-1][j-1]转移
来;g[i][j]考虑枚举第一棵树的大小k，从一棵树和一个森林转移来，同时还要乘上第一棵子树大小为k的概率，我们有状态转移方程：g[i][j] = f[k][j] ∗ g[i − k][j] ∗ dp[i][k]
最后只要用f[n][j]-f[n][j-1]就可以得到深度为j的树的概率
（初始化看代码把）
以下代码：
#include#define il inline#define LL long long#define _(d) while(d(isdigit(ch=getchar())))using namespace std;const int N=205;int n,p;LL dp[N][N],inv[N],g[N][N],f[N][N],ans;il int read(){ int x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return f*x;}il LL ksm(LL a,int y){LL b=1;while(y){ if(y&1)b=b*a%p;a=a*a%p;y>>=1;}return b;}int main(){ n=read();p=read();dp[1][1]=1;for(int i=1;i<=n;i++)inv[i]=ksm(i,p-2); for(int i=2;i<=n;i++)for(int j=1;j<=i;j++) dp[i][j]=(dp[i-1][j-1]*(LL)(j-1)%p*inv[i]%p+dp[i-1][j]*(LL)(i-j)%p*inv[i]%p)%p; for(int i=0;i<=n;i++)g[0][i]=1;f[1][0]=1; for(int i=1;i<=n;i++)for(int j=0;j<=n;j++){ if(j>0)f[i][j]=g[i-1][j-1]; for(int k=1;k<=i;k++){ g[i][j]=(g[i][j]+f[k][j]*g[i-k][j]%p*dp[i][k]%p)%p; } } for(int i=1;i<=n;i++)ans=(ans+(LL)i*(f[n][i]-f[n][i-1]+p)%p)%p;printf("%d\n",ans); return 0;}