题解：P7111 青春有悔

· · 题解

一道有意思的计数题。算概率相当于合法的情况，因为总情况是容易得到的。我们思考如何表示出某一种得分的情况，这个显然用生成函数刻画。对于第 i 天我们用生成函数 F_i(x)=\sum\limits_{k=0}^{a_i} x^k 表示，显然它还有封闭型式：1-x^{a_i+1}\over1-x。于是我们就能方便地表示出考试的情况了：

G=\prod_{i=1}^n{1-x^{a_i+1}\over1-x}

考虑到合法的情况是一段后缀，于是我们运用 P5488 的一点小技巧，令 G\leftarrow G\times{1\over1-x}，然后就变成了求单点的信息。观察到后面的询问都是在最开始状态的基础上单点修改，所以考虑快速求出 G 然后通过 G 直接求答案。

我们接下来处理 G。考虑对其进行化简：

G=\left({1\over1-x}\right)^{n+1}\prod_{i=1}^n(1-x^{a_i+1})

我们分别处理出前后两部分最后再拼到一起。先考虑前面的部分，我们尝试广义二项式定理：

\begin{aligned} \left({1\over1-x}\right)^{n+1}&=(1-x)^{-n-1}\\ &=\sum_{i=0}^\infty{-n-1\choose i}(-x)^i\\ &=\sum_{i=0}^\infty(-1)^i{i-(-n-1)-1\choose i}(-x)^i\\ &=\sum_{i=0}^\infty{n+i\choose i}x^i\\ \end{aligned}

其中第三行运用上指标反转。这样我们轻松得到了前半部分，接下来考虑后面怎么搞。注意到后面有 \mathcal O(n) 个少项式进行 \prod 运算，于是考虑 P4389 的技巧，通过 \exp\ln 将连乘变成连加。不考虑 \exp 现在我们要处理的是：

\sum_{i=1}^n\ln(1-x^{a_i+1})

注意到有 -\ln(1-x)=\sum\limits_{i=0}^\infty{x^i\over i}，所以有：

\sum_{i=1}^n\ln(1-x^{a_i+1})=-\sum_{i=1}^n\sum_{j=1}^\infty{x^{(a_i+1)j}\over j}

证明上面的式子是相等的方法考虑对两边同时求导。所以后半部分调和级数枚举即可求得。现在加入单点修改我们就直接写式子了：

ans=[x^{b-1}]{1-x^{a+1}\over1-x^{a_p+1}}G=[x^{b-1}]{G\over1-x^{a_p+1}}-[x^{b-a-2}]{G\over1-x^{a_p+1}}

于是我们需要处理两个形如 [x^b]{G\over1-x^a} 的式子。注意到一次询问中的 a 会对 ka,k\in \mathbb Z+ 的位置产生影响所以考虑根号分治，对于 a\le\sqrt n 的情况我们提前对每个 a 都暴力算出每一位的值并记下来，询问的时候直接 \mathcal O(1) 查；对于 a>\sqrt n 的时候因为需要改的位置很少于是就在询问时暴力改即可，时间复杂度 \mathcal O(n\ln n+n\sqrt n)。