官方题解！
首先令 v=V+2。
考虑一个结点 [l,r]。
则实际上一次操作对它产生影响的概率即这次操作的区间包含它的概率，即 p=\frac{l(n-r+1)}{\binom{n+1}2}。
设随机加 k 次 [-1,V] 中的整数，结果为 0 的方案数为 f_k，那么枚举被操作次数，一个结点的贡献即为
\sum\limits_{i=0}^m \binom mi p^i (1-p)^{m-i} \left(1-\frac{f_i}{v^i}\right)
观察到这其实是一个关于 \frac p{1-p} 的多项式乘一个 (1-p)^m，设其等于 (1-p)^m \sum\limits_{i=0}^m c_i \left(\frac p{1-p}\right)^i
一个简单的做法是直接多点求值，只要常数不爆炸应该都可以过。
不过存在不多点求值的做法。
将有贡献的结点（非叶结点）任意标号为 1,2,\dots,n-1，令 p_i 表示第 i 个结点的以上提到的 p 值，令 a_i = \frac{p_i}{1-p_i},b_i = (1-p_i)^m，则总答案为 \begin{aligned} \sum\limits_{i=1}^{n-1} b_i \sum\limits_{j=0}^m c_j a_i^j &= \sum\limits_{j=0}^m c_j \sum\limits_{i=1}^{n-1} b_i a_i^j \end{aligned}
于是问题变为对 j=0,1,\dots,m 求出 \sum b_i a_i^j。
发现
\sum\limits_{i=1}^{n-1} b_i a_i^j = [x^j] \sum\limits_{i=1}^{n-1} \frac{b_i}{1-a_ix}
可以考虑分治 NTT 实现通分并相加的过程，时间复杂度 O(n \log^2 n)。
接下来，问题只剩下求出 f_k。
通过组合数最后可以推得一个 O\left(\frac {m^2}V\right) 的做法，可以参见出题人的题解，这里略去不谈。
通过大力生成函数处理，显然
f_k = [x^0](x^{-1}+1+x+x^2+\dots+x^{V})^k
令 F(x) = x^{-1}+1+x+x^2+\dots+x^{V} = \frac{1-x^v}{x(1-x)}
然后问题变成 [x^0] F^k(x)
事实上这个问题的形式与一个经典问题极其相似，于是这启发我们考虑拉格朗日反演。
但是由于要提取常数项，所以并不能直接运用经典的拉格朗日反演；并且，F 显然不存在复合逆。
考虑令 G = \frac1F，令 H 为 G 的复合逆，然后考虑另类拉格朗日反演： [x^0] F^k(x) = [x^0] G^{-k}(x) = [x^k] \frac{xH'(x)}{H(x)}
至此，如果能求出 H(x)，问题即迎刃而解。
注意到
G = \frac{x(1-x)}{1-x^v}
代入 x = H 得 xH^v - H^2 + H - x = 0
使用多项式牛顿迭代求解即可。
时间复杂度 O(n \log^2 n)（视 n,m 同阶）。
代码：
1 |
|