题解 P7111 【青春有悔】

本文给出一个 $\tilde O(n^{4/3})$ 的算法（下文均认为 $n,q$ 同阶，且用 $\tilde O$ 符号避免 $\log$ 因子的讨论），虽然复杂度较优，但其所带的 $\log $ 因子以及常数因子使其在目前的数据范围内并没有太大的优势。（[这里](https://www.luogu.com.cn/record/43107202)是一个实现） ------------- 让我们先来回顾一下前面不太关键的部分，设 $f(x) = \sum_{n\ge 0} a_n x^n$ 为总分数为 $n$ 的方案数的生成函数，那么考虑计数总分小于 $y$ 的情况，这无非就是 $$ [x^{y-1}] \frac 1{1-x} f(x) $$ 根据诸个比赛日相互之间的独立性，$f(x)$ 可确定为一个简单的乘积式 $$ f(x) = \prod_{i=1}^n \frac{1-x^{a_i+1}}{1-x} $$ 即 $g(x) = \frac 1{1-x} f(x)$，那么考虑整理各 $(1-x^k)$ 指数上的幂次，可得到整数数列 $c_k$，满足 $$ \begin{aligned} g(x) &= \prod_{k\ge 1} (1-x^k)^{c_k}\\ &= \exp\left(\sum_{k\ge 1} c_k \ln (1-x^k)\right)\\ \end{aligned} $$ 注意到这是可以 $\Theta(n\log n)$ 计算的。 而对于每次询问，设其将一个原本在 $[0, s]$ 内的分数改为了 $[0, t]$，那么我们询问的实则就是 $$ \begin{aligned} & \quad [x^{y-1}] \frac{1-x^{t+1}}{1-x^{s+1}} g(x)\\ &= \left([x^{y-1}] - [x^{y-t-2}]\right) \frac 1{1-x^{s+1}} g(x) \end{aligned} $$ 因此，我们将问题转化为了如下情况：多次给出 $m, k$，询问 $[x^m] \frac 1{1-x^k} g(x)$，也即 $$ \sum_{j\ge 0} g_{m-jk} $$ -------------- 接下来给出解决转化后问题的关键。我们首先考虑一个稍微弱一点的问题，即给出 $0\le r < k$，求 $$ \sum_{j \bmod k = r}g_j $$ 这个问题不难写做生成函数的形式： $$ [x^r] g(x) \bmod (x^k-1) $$ 因此我们不妨令 $B$ 为阈值，预处理对于所有的 $k\le B$，其 $g(x) \bmod (x^k-1)$，这通过经典的分治取模可得一个复杂度为 $\tilde O(n + B^2)$ 的算法。 因此复杂度为 $\tilde O(n + B^2 + \frac {n^2}B)$，不难得到当 $B = \tilde O(n^{2/3})$ 的时候渐进复杂度的指数取到最优，为 $\tilde O(n^{4/3})$。 而对于原问题呢？实际上这可以通过加一层分治，每层都按照本层的 $B=\tilde O(n^{2/3})$ 进行预处理，那么预处理的复杂度为 $T(n) = 2T(n/2) + \tilde O(n^{4/3})$，这还是 $T(n) = \tilde O(n^{4/3})$ 的。而一次询问是 $Q(n) = Q(n/2) + \tilde O(n^{1/3})$ 的，因此询问还是 $\tilde O(n^{1/3})$ 的。 综上，我们就得到了一个 $\tilde O(n^{4/3})$ 的做法。