洛谷 7445. 「EZEC-7」线段树 | Alpha1022's Blog

[Alpha1022]

https://www.alpha1022.me/articles/lg-7445.htm

官方题解！ 首先令 (v=V+2)。 考虑一个结点 ([l,r])。 则实际上一次操作对它产生影响的概率即这次操作的区间包含它的概率，即 (p=\frac{l(n-r+1)}{\binom{n+1}2})。 设随机加 (k) 次 ([-1,V]) 中的整数，结果为 (0) 的方案数为 (f_k)，那么枚举被操作次数，一个结点的贡献即为 [ \sum\limits_{i