原理
快速数论变换(FNT)
原理同FFT一样,用与弧度具有同样性质的一组值替代弧度进行计算,具体性质如下:
FFT 中能在 O(nlogn) 时间内变换用到了单位根 的什么性质:
$\omega_n^n = 1$
, , ⋯, 是互不相同的,这样带入计算出来的点值才可以用来还原出系数
, ,这使得在按照指数奇偶分类之后能够把带入的值也减半使得问题规模能够减半
这点保证了能够使用相同的方法进行逆变换得到系数表示
参考:
多项式逆元
参考:
多项式除法及求模
参考:
多项式多点求值与拉格朗日插值
参考:
实现
展开代码
1 | /* |
应用
多项式快速乘
展开代码
1 | int main() { |

多项式逆元
展开代码
1 | int main() { |
输入数据得到输出后的结果如下图

多项式除法以及取模
展开代码
1 | int main() { |

多项式多点求值
展开代码
1 | int main() { |
输入数据后得到结果如下

拉格朗日快速插值计算
展开代码
1 | int main() { |
输入数据得到的结果如下
