多项式指定大小的单位根点值式求解(含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]\)，可以得到合并式子

\(\begin{aligned} 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}})\end{aligned}\)

对于\(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)