自动搬运

查看原文

来自洛谷，原作者为

	Elegia irony

搬运于2025-08-24 22:26:44，当前版本为作者最后更新于2020-11-28 23:42:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

本文给出一个 $\tilde O(n^{4/3})$ 的算法（下文均认为 $n,q$ 同阶，且用 $\tilde O$ 符号避免 $\log$ 因子的讨论），虽然复杂度较优，但其所带的 $\log$ 因子以及常数因子使其在目前的数据范围内并没有太大的优势。（这里是一个实现）

---

让我们先来回顾一下前面不太关键的部分，设 $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})$ 的做法。