大佬教程收集整理的这篇文章主要介绍了题解：玩具，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
概率期望DP，其DP性质发现于随n的递变，问题空间呈规律性变化
通常情况下，期望问题有两种基本解决思路：1.计算出总贡献除以总情况数
2.计算出子问题概率，利用定义，再乘以子问题对应贡献即可
首先想到思路一，设计f[i][j]表示进行到第i轮，子树最大深度为j的情况数
考虑如何转移，想到的是将第i次操作在叶节点进行，由i-1进行拓展，发现
需要维护当前阶段第j层叶节点数，O(n^3)可行，然而发现每一层节点都由上
一层节点进行转移，时间复杂度O(n^4)，（当然，矩阵优化O(n^3*logn)卡常
可做，如果不嫌麻烦），于是当事一直思考如何优化，事实上这是错误的策略
通常情况下我们并不能一下子想到正确DP，此时应考虑更换思路
事实上思路一还有一种做法，转化为计数DP即可（这也是第一种思路的本质）
考虑给树定形，发现1，2节点的位置相对固定，而树形DP本质问题是子树与
父树的相互关系，在1，2节点固定后，我们并不需要考虑每一种树形态，问题
在于树的期望深度，那么DP过程只需要转移子树深度，大小，分别考虑以1，2
节点为根，乘法计数，即可O(n^4)，这种思考方式的有点在于并不去考虑与问题无
关的树形，而是将所有树形化归为一种抽象形态，避免了具体考虑转移的繁杂，
个人认为相较于第一种方法更优
上述两种方式均以计数DP方式计算总贡献进而推出期望，但是其并不适用与
本问题，本问题更接近与抽象问题，因为在阶段推进过程中，仅仅是生成树，树
的形态不定，也就是没有统一的转移方式，具体思考会陷入陷阱。
于是我们考虑抽象思考，绕过树形态的变化，采取第二种思路，宏观考虑从
一种形态转化为另一种形态的概率。转移无定式，对于本题更是如此，考虑对于
当前树，他是如何被生成的。因为对于生成方式完全无描述，我们可以认为，第
一种情况是有子树在叶节点拓展生成，另一种情况是由新节点连接若干子树行形成。
发现第二种情况显然比第一种情况简洁，于是对于i个节点，j深度子树生成概率
就由i-1节点，最大深度等于j-1的森林生成概率转移而来，于是可以并行DP
（很多情况下，当一中DP无法进行时，可以利用多DP并行，记录所需信息来辅助
主DP转移），发现对于森林概率的DP，其最优子结构由子森林与子树构成，也就
是说森林与树生成概率的转移相辅相成，基本完成。
当然存在一个问题为森林的转移存在概率限制，即另需记录i节点j深度森林中
某棵树为k节点概率，由于这棵树的编号是等效的，故数学归纳得概率为1/i
代码如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define I int 4 const I MAXN = 205; 5 I n,mod,res; 6 I f[MAXN][MAXN],g[MAXN][MAXN],d[MAXN]; 7 inline I qpow (I base,I index) { 8 I res(1); 9 for ( ; index ;index >>= 1,base = 1ll * base * base % mod) 10 if (index & 1) res = 1ll * res * base % mod; 11 return res; 12 } 13 signed main () { 14 cin >> n >> mod; 15 for (I i(1);i <= n; ++ i) d[i] = qpow (i,mod - 2); 16 for (I i(0);i <= n; ++ i) f[1][i] = g[1][i] = g[0][i] = 1; 17 for (I i(2);i <= n; ++ i) 18 for (I j(0);j <= n; ++ j) { 19 if (j) f[i][j] = g[i - 1][j - 1]; 20 for (I k(1);k <= i; ++ k) 21 g[i][j] = (g[i][j] + 1ll * f[k][j] * g[i - k][j] % mod * d[i]) % mod; 22 } 23 for (I i(1);i <= n; ++ i) 24 res = (res + 1ll * (f[n][i] - f[n][i - 1]) * i) % mod; 25 cout << (res + mod) % mod << endl; 26 }
以上是大佬教程为你收集整理的题解：玩具全部内容，希望文章能够帮你解决题解：玩具所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。
