题解 P5548 【[BJ United Round #3] 押韵】

· · 题解

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

算法一

时间复杂度 $\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}$ 的线性组合。