P8561 送别（Farewell）

· · 题解

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

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

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

这可以用第一类 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 $$\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)$，代码就不贴了（