题解 P5577 【[CmdOI2019]算力训练】

一些解释以及复杂度的明确。 假设我们的模数是一个性质比较好的质数 $p$，满足在 $\mathbb F_p$ 上方程 $\omega^k=1$ 有 $k$ 个互异根，这就可以直接对问题施加高维 DFT，俗称“单位根反演”或者 FWT 等。也就是首先任取本源单位根 $\Phi_k(\omega)=0$。 其中为了求算 $$ f_{x_0x_1x_2\dots x_{m-1}} = \prod_{y=y_0y_1\dots y_{m-1}} (1+\omega^{\sum_{i=0}^{m-1}x_iy_i})^{cnt_y}$$ 我们需要添加占位多项式取模 $x^k-1$，通过 $$\prod_{y=y_0y_1\dots y_{m-1}} cnt_yx^{\sum_{i=0}^{m-1}x_iy_i}$$ 的计算来得到每个 $(1+w^i)$ 需要做幂的上指标。事实上我们发现上述变换其实还是一个高维各自独立的变换，我们按照类似 FWT 的形式做转移，只需要做 $m k^{m-1}$ 次变换，每次可以在 $\Theta(k^3)$ 甚至 $\Theta(k^2\log k)$（不实用）的时间完成变换，这部分的时间复杂度是 $\Theta(mk^{m+2})$ 甚至 $\Theta(mk^{m+1}\log k)$。 我们考虑用占位多项式来先代替扩域。预见到我们的过程中没有发生除法，那么所有的运算都是可进行的。而注意到模 $x^k-1$ 有零因子，这等价于一个“数”被给出了多种表示。考虑本原多项式 $\Phi_k(x)$，由于在 $k=5,6$ 时本原多项式分别是 $x^4+x^3+x^2+x+1$ 和 $x^2-x+1$，经验证它们都不可因式分解。 > 如何验证？$\mathbb F_p$ 上的多项式的不可约性检测方法是验证充要条件：$f | (x^{p^n}-x)$ 且对任意素数 $t | n$，有 $\gcd(x^{p^{n/t}}-x,f) = 1$。 根据定义有 $\Phi_k(x) | x^k-1$，因此 $(f\bmod x^k-1)\bmod \Phi_k(x) = f \bmod \Phi_k(x)$，我们只需在原本占位多项式算得的结果基础上再进行这样一次约化，由于 $\bmod \Phi_k(x)$ 系没有零因子，所以这个环是域，因而我们可以断言取模完了之后只剩下常数项。 接下来考虑 $(1+x)^r$ 的计算，容易发现我们每个上指标 $r\le n$，所以可以通过分块预处理 $\Theta(wn^{1/w} k^2)$，单次询问 $\Theta(wk^2)$。实际上取 $w=2$ 就已经对效率没什么影响了。因为一项的乘积就是要计算 $\prod_i (1+w^i)^{r_{x,i}}$，我们要将若干 $\prod_i F_{x,i}(w^i)$ 相乘，第 $i$ 个在 $x^j \rightarrow x^{ij \bmod k}$ 下标变换后可以认为是 $k/\gcd(i,k)$ 项的，总共乘法消耗可以认为是 $\Theta(k\sum_{d|k} \varphi(d)d) = \Theta(k^3)$，此时 $\Theta(wk^3)$ 在 $w$ 取常数时是同阶的。 因此这种方法的复杂度是 $\Theta(nk + mk^{m+2} + wn^{1/w}k^2 + wk^{m+3})$。