一、问题小 C 有一棵苹果树树上每个节点都恰好拥有两个分支空位。生长规则第 1 天生成根节点此时根节点有 2 个空分支第 i 天i≥2i\ge2i≥2树上存在若干未长出节点的空分支随机等概率选一个空分支在该分支处新增一个节点新节点与原节点连边新节点自带 2 个空分支。定义不便度树上所有无序点对(u,v),u≠v(u,v),u\neq v(u,v),uv的距离之和两点距离为两点路径上边的条数。设生长 N 天后树不便度的数学期望为 E。保证E⋅N!E\cdot N!E⋅N!是整数求(E×N!) mod P(E \times N!) \bmod P(E×N!)modP。二、算法思路整个算法可以概括为以下五步Step 1预处理阶乘计算fac[i]i!fac[i] i!fac[i]i!用于统计所有生成顺序的数量。Step 2DP 统计子树大小f[i][j]f[i][j]f[i][j]表示所有 i 个结点的生成过程中子树大小为 j 的结点总出现次数。Step 3状态转移新结点长在该子树外子树大小不变对应系数 i-j-1。新结点长在该子树内子树大小增加 1对应系数 j。新结点本身形成一个新的叶子贡献i!i!i!。Step 4统计每条边的贡献若某结点子树大小为 j则其与父亲之间的边贡献为j(n−j)j(n-j)j(n−j)。Step 5累加所有贡献将所有子树大小对应的贡献求和得到所有生成过程的不便度总和即题目要求的E×N!E × N!E×N!最后对modmodmod取模三、算法过程#includebits/stdc.husingnamespacestd;usinglllonglong;constintN2005;ll f[N][N];ll fac[N];intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;ll mod;cinnmod;fac[0]1;for(inti1;in;i)fac[i]fac[i-1]*i%mod;// 计算阶乘for(inti1;in;i){for(intj1;ji;j){f[i][j](f[i-1][j]*(i-j-1)// 长在子树外f[i-1][j-1]*j// 长在子树内(j1?fac[i]:0)// 形成新叶子)%mod;}}ll ans0;for(intj1;jn;j){ans(ansf[n][j]*j%mod*(n-j))%mod;}coutans%mod\n;return0;}
)
