自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:40:09，当前版本为作者最后更新于2022-10-03 17:31:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

首先观察题意可以发现，每次事件的两步，分别对应了两类 Stirling 数的定义。于是有一个朴素的计算式：

$$\sum_{i=0}^n \begin{Bmatrix} a_i+k \\ a_i\end{Bmatrix}\begin{bmatrix} a_i \\ a_i-k\end{bmatrix} $$

要优化做法，需要的第一个重要性质是：

$\begin{bmatrix} x \\ x-k\end{bmatrix}$ 关于 $x$ 是一个 $2k$ 次多项式。

这可以用第一类 Stirling 数每列的 EGF 来证明：

$$\begin{bmatrix} n \\ k\end{bmatrix}= n!(-1)^{n-k}[z^n]\frac{\ln(1+z)^k}{k!} $$

进行 Lagrange 反演：

$$\begin{bmatrix} n \\ k\end{bmatrix}=\frac{n!}{k!}(-1)^{n-k}\frac{k}{n}[z^{n-k}]\left( \frac{z}{\text e^z-1}\right)^n $$$$= \frac{(n-1)!}{(k-1)!}(-1)^{n-k}[z^{n-k}]\left( \frac{z}{\text e^z-1}\right)^n $$

因此

$$\begin{bmatrix} x \\ x-k\end{bmatrix} = (x-1)^{\underline k}(-1)^k [z^k]\left( \frac{z}{\text e^z-1}\right)^x $$

将要提取 $z^k$ 系数的那一块东西展开，可以发现这部分确实是一个 $k$ 次多项式，故整体就是一个关于 $x$ 的 $2k$ 次多项式。

现在我们可以设

$$S_k(x) = \begin{bmatrix} x \\ x-k\end{bmatrix}$$

由 Stirling 数反射公式可知

$$\begin{bmatrix} n \\ k \end{bmatrix} = \begin{Bmatrix} -k \\ -n \end{Bmatrix} $$

于是

$$\begin{Bmatrix} x+k \\ x \end{Bmatrix}= \begin{bmatrix} -x \\ -x-k\end{bmatrix}=S_k(-x) $$

现在，对于 $q=2$ 的数据已经有了一种做法。首先我们需要求出 $S_k(x)$ 的系数，而这个问题的瓶颈在于求：

$$[z^k]\left( \frac{z}{\text e^z-1}\right)^x$$

$x$ 在指数上不方便操作，取 $\ln$ 再做 $\exp$ 就变成

$$\sum_{i=0}^k \frac{x^i}{i!}[z^k] \left( \ln \frac{z}{\text e^z-1}\right)^i \ \ \ (*) $$

再次使用 Lagrange 反演，设

$$F(z) = \ln \frac{z}{\text e^z-1}$$ $$\text e^z= \frac{F^{\langle -1\rangle}(z)}{\text e^{F^{\langle -1\rangle}(z)}-1} $$

$F^{\langle -1 \rangle}(z)$ 系数可以用牛顿迭代以 $\Theta(k \log k)$ 的时间复杂度求解，于是

$$(*) = \frac 1k\sum_{i=0}^k \frac{ix^i}{i!} [z^{k-i}]\left( \frac{z}{F^{\langle -1 \rangle}(z)}\right)^k $$

可以 $\Theta(k \log k)$ 的时间复杂度求出，故 $S_k(x)$ 的系数也可以这个复杂度求出。
现在设 $G(x) = S_k(x)S_k(-x)$，由于 $q=2$ 时 $a_i=i$，答案可以写为：

$$\sum_{j=0}^{4k}g_j \sum_{i=1}^ni^j$$

如何以 $\Theta(k \log k)$ 的时间复杂度求出 $j \in [0,k]$ 时的正整数幂和也很经典：

$$\sum_{k=0}^\infty \frac{x^k}{k!}\sum_{i=0}^ni^k = \sum_{i=0}^n \text e^{ix}=\frac{1-\text e^{(n+1)x}}{1-\text e^x} $$

于是 $q=2$ 的情况就能以 $\Theta(k \log k)$ 的复杂度解决。

对于 $q \neq 2$，求出 $G(x)$ 的步骤是类似的。设

$$A = \frac{1}{\sqrt{q^2-4}} \ , \ r=\frac{q \pm \sqrt{q^2-4}}{2} $$

则有 $a_i=A(r_1^i-r_2^i)$，也可以类似地将答案写为

$$\sum_{j=0}^{4k}g_j A^j\sum_{i=1}^n (r_1^i-r_2^i)^j $$

如果暴力进行二项式展开，可以做到 $\Theta(k^2)$ 的时间复杂度。对于一般的情况优化是困难的，不过这里的特征根满足 $r_1r_2=1$，这也就是第二个重要性质。

设 $r_1 = \alpha$，$r_2 = \alpha^{-1}$，求出 $\tilde G(x)=G(Ax-Ax^{-1})$ 的系数后，则答案可以写为

$$\sum_{j=-4k}^{4k}\tilde g_j\sum_{i=1}^n \alpha^{ij} $$

然后就能以 $\Theta(k + \log n)$ 的时间复杂度算出答案了。那么现在的主要问题就是如何求 $\tilde G(x)$。

再回看 $G(x)=S_k(x)S_k(-x)$，这使得 $G(x)$ 的奇数次项都是零。这带来了一个很好的性质：$\tilde G(x)$ 的系数不用扩域表示！这可以大幅优化常数。

具体来说，令 $H(x^2/A^2)=G(x)$，那么只需要求出 $H(x+x^{-1}-2)$ 的系数后，把 $x$ 都代换为 $x^2$ 就得到了 $\tilde G(x)$。

有负数次项不便于处理，我们考虑求出

$$x^{2k}\sum_{i=0}^{2k}h_i (x+x^{-1}-2)^i$$ $$=x^k \left( x^k \sum_{i=0}^k h_i (x+x^{-1}-2)^i\right)+(x-1)^{2k+2}\left( x^{k-1} \sum_{i=0}^{k-1} h_{i+k+1}(x+x^{-1}-2)^i\right) $$

可以分治求解，时间复杂度 $\Theta(k \log^2 k)$。

于是总时间复杂度就是 $\mathcal O(k \log^2 k +\log n)$，代码就不贴了（