自动搬运

查看原文

来自洛谷，原作者为

	Elegia irony

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

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

以下是正文

---

一些解释以及复杂度的明确。

假设我们的模数是一个性质比较好的质数 $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})$。