多项式指定大小的单位根点值式求解(含Bluestein’s Algorithm)

下面的阐述建立于存在 \(n\) 阶单位根的前提下。

（如果是NTT，必须满足 \(n|(P-1)\) ，否则单位根可能会变成一个复杂的多维向量）。

\[ \ \]

用卷积解决多项式与点值式的转化:Bluestein’s Algorithm

设最终求得的点值式为 \(f(x^k)=\sum a_i\cdot \omega_n^{i k}\)。

其中指数为 \(ik\) ，有一种简单的转化 \(i\cdot k=\cfrac{i^2+k^2-(i-k)^2}{2}\)。

由于在模意义下， \(x^{\frac{i}{2}}\) 次(二次剩余)是一个非常麻烦的东西，所以考虑一个更优的转化。

\[ i\cdot k=C(i+k,2)-C(i,2)-C(k,2) \] 这条式子的组合意义是：从集合 \(i,k\) 分别选一个，等价于从 \(i+k\) 选两个减去在 \(i,k\) 内部选两个。

通过这样的转化，我们可以对于每一个 \(a_i\) 计算其对于每个 \(f(x^k)\) 的贡献，

具体过程是简单的构造卷积，这里省略。

适用于特殊情况的转化方法

需要了解的是，多项式卷积的 FFT / NTT 不止适用与于二元分治。

对于多项式 \(F(x)\) 的 \(d\) 元分治，设分治子问题的答案为 \(G_j(x'_i),j\in[0,d-1]\) ，可以得到合并式子：

\[ F(x_i)=\sum_{j=0}^{d-1}x_i^jG_j(x_i^d)=\sum_{i=0}^{d-1}x_i^jG_j(x'_{i\mod \frac{n}{d}}) \] 对于 \(n\) 进行质因数分解，得到 \(n=\prod p_i\) ，带入上面的式子，带入 \(p_i\) 元分治强行求解，可以认为最终复杂度为 \(O(n\sum p_i)=O(n\cdot \max\{p_i\} \log n)\)。

因此，这种方法使用于 \(p_i\) 较小的情况。

n 元点值式的用途

DFT 的卷积是溢出的， \(x^i\) 会溢出到 \(x^{i\mod n}\) ，系数之间存在着循环关系。

我们可以利用 \(n\) 元卷积做到指定大小的循环卷积，可以处理一些特定问题。

例题: [CTSC2010]性能优化（使用 \(O(n\log n\log C)\) 的快速幂无法通过，尚未尝试Bluestein’s Algorithm）。