题解 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})。