题解 P6108 【[Ynoi2009]rprsvq】

> upd: 已尝试修复在博客区公式渲染问题，如还不行请在博客中查看。 来推广一下积分邪教w 首先记 $r - l + 1 = L$，以及一段区间我们容易维护 $s_1 = \sum_i x^2$ 和 $s_2 = \sum_{i\neq j} x_ix_j$，那么可知答案是 $$ s_1 \left [\sum_{k=0}^{L - 1} \binom {L-1}k \left(\frac1{1+k} - \frac1{(1+k)^2}\right)\right] - s_2\left( \sum_{k=0}^{L-2} \binom{L-2}k \frac1{(2+k)^2} \right) $$ （先验地，我们其实知道一切这种超几何求和式都存在共性，所以可以预判应该是 $\Theta(n)$ 把这些都算出来。而本题中求和还是形式偏简单的。） 首先看如何计算 $\sum_{k=0}^n \binom nk \frac1{1+k}$，这显然可以表为有理积分 $$ I_n = \sum_{k=0}^n \binom nk \int_0^1 x^k\, \mathrm{d}x=\int_0^1 (1+x)^n \,\mathrm d x = \left.\frac1{n+1}(1+x)^{n+1}\right|_0^1 = \frac{2^{n+1}-1}{n+1} $$ 而我们容易得到将 $\frac1{(n+1)x}((1+x)^{n+1} - 1)$ 在 $[0, 1]$ 上积分就给每一项再除了一个 $1+k$，注意到 $$ \begin{aligned}\frac1{n+1} \int_0^1 \frac1{x}((1+x)^{n+1} - 1)\,\mathrm d x & = \frac1{n+1} \int_0^1 \frac{(1+x)^{n+1} - 1}{(1+x)-1}\,\mathrm d x\\ &= \frac1{n+1} \int_0^1 \sum_{k=0}^n (1+x)^k\,\mathrm d x\\ &= \frac1{n+1} \sum_{k=0}^n I_k \end{aligned} $$ 只需对之前得到的数列做前缀和即可。 最后我们处理 $\sum_{k=0}^n \binom n k \frac1{(2+k)^2}$，类似的，这个首先考虑除以一次 $2+k$，得到 $\int_0^t x(1+x)^n \,\mathrm d x$，只需进行分部积分即可转化： $$ \begin{aligned} &\quad \int_0^t x(1+x)^n \,\mathrm d x \\ &= \int_0^t x\,\mathrm d\left( \frac1{n+1} (1+x)^{n+1} \right) \\ &= \left.\frac{x(1+x)^{n+1}}{n+1}\right|_0^t - \int_0^t \frac{(1+x)^{n+1}}{n+1} \,\mathrm{d}x\\ &= \left.\frac{x(1+x)^{n+1}}{n+1} - \frac{(1+x)^{n+2}}{(n+1)(n+2)}\right|_0^t\end{aligned} $$ 再积一遍就没有什么新意了，不予赘述，读者可自行尝试。 > 相比解这道题，可能解标题更有趣一些：Range Plus Range Subsequence Variance Query.（区间加区间子序列方差查询。）