自动搬运

查看原文

来自洛谷，原作者为

	Elegia irony

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

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

以下是正文

---

事实上本题是 UOJ #450. 【集训队作业2018】复读机 的一个加强版。

算法一

$n\le 5\times 10^4$，我可以做多项式快速幂！这个多项式就是 $(\sum_{j\ge 0} \frac{x^{jd}}{(jd)!})^k$。这个模数不太友好，你可能需要 MTT……常数应该很大。

时间复杂度 $\Theta(n\log n) \sim \Theta(n\log n \log k)$，前者是进行多项式 $\ln , \exp$ 达到的复杂度，但是常数可能很大。

预计得分 $20\%$。

算法二

我们考察 $(\sum_{j\ge 0} \frac{x^{jd}}{(jd)!})^k$ 可以如何表示。

事实上与周期函数有关的，我们可以自然想到类似 DFT 的形式，也就是考虑到 $\sum_{j=0}^{d - 1} \omega_d^{cj} = d[d | c]$，因此我们可以知道上面的那个多项式实际上是

$$\frac1d \sum_{j=0}^{d-1} \exp \omega_d^j x$$

我们直接枚举拆括号的过程中计算了几个 $\exp \omega_d^0 x$，几个 $\exp \omega_d^1 x$……然后这一部分的贡献就是 $(c_0 + c_1 \omega_d^1 + c_2 \omega_d^2 + \dots)^n$。最后总和除以 $d^k$。

时间复杂度 $\Theta(k^{d-1}\log n)$，预计得分 $50\%$。

算法三

主要思想还是围绕优化计算下式：

$$[x^n]\left( \frac1d \sum_{j=0}^{d-1} \exp \omega_d^j x \right)^k $$

对于 $d=4$ 的情况，我们实际上是只需要统计每个 $\exp (a + b\mathrm{i})x$ 出现多少次。通过推导一些式子，或者直接将复平面旋转 $45^\circ$ 我们可以得到，方案数是 $\displaystyle\binom{k}{\frac{k + |a+b|}2} \binom{k}{\frac{k + |a-b|}2}$。因此答案可以在 $\Theta(k^2 \log n)$ 内计算出来。

预计得分 $70\%$。

算法四

对于 $d=6$ 的情况，我们注意到 $\omega_6$ 的代数关系有 $\omega - 1 = \omega^2$，因此所有的根都可以用 $1, \omega$ 表示，即给每个数赋予了一个离散的二维坐标

$$\begin{array}{clclc} \omega^0 & = & 1 & & \\\omega^1 & = & & & \omega\\\omega^2 & = & -1 & + & \omega\\\omega^3 & = & -1 & & \\\omega^4 & = & & &-\omega\\\omega^5 & = & 1 & + &-\omega\end{array} $$

因此我们只需要做一个二维的快速幂，倍增 FFT 可以做到 $\Theta(k^2 \log k)$。但是常数可能较大。

预计得分 $80\% \sim 100\%$。

算法五

考虑计算一个二元母函数的高阶幂，$G(x, y) = F(x, y)^k$，可以得到 $F \frac{\partial G}{\partial_x} = kG \frac{\partial F}{\partial_x}$，由此可列得递推式子解出所有系数。计算高阶幂的复杂度是 $\Theta(k^2)$ 的。复杂度 $\Theta(k^2 \log n)$ 且常数较小。

事实上这也是可以直接用来做 $k=4$ 的情况的。

预计得分 $100\%$。

further

对于更大的 $d$，我们期望能得到一个怎样的做法？考虑 $d$ 次单位根的代数关系，我们希望能够基于一个它们的有理系数线性组合的基。由此则能将维度缩到基的维度，在其上进行快速幂。

我将说明维度可以达到 $\varphi(d)$，而数学迷告诉我说通过一些关于域的理论可以证明这也是下界，等我学了之后补一下证明。

考虑分圆多项式 $\Phi_d(x) = \prod_{0\le k < d, \gcd(d, k) = 1} (x - \omega_d^k)$，它的次数显然是 $\varphi(d)$。

显然分圆多项式也可以用容斥原理重写，即

$$\Phi_d(x) = \prod_{k|d} (x^{d/k}-1)^{\mu(k)}$$

显然该多项式的系数都是整数。由于 $\Phi_d(\omega_d) = 0$，不难得到 $\omega_d^k = \left.x^k \bmod \Phi_d\right \vert_{x=\omega}$。因此这个多项式的取模自然而然地导出了每个单位根到 $1, \omega_d, \dots, \omega_d^{\varphi(d) - 1}$ 的线性组合。