清华集训总结

任意模数的FFT

shinbokuow posted @ Jan 05, 2016 03:54:59 PM in Something with tags FFT 中国剩余定理 NTT , 2099 阅读

 

我现在也不知道是不是对的,反正也只是口胡,如果有错误的话请大家指出。

我们使用NTT对两个长度均为$n$的序列进行FFT,需要模数$P$为质数,且$P=2^{k}+1$,其中$2^k\geq{n}$。

这样的话,并不是所有的模数都能满足这个条件的。

但是,我们考虑直接算出卷积而不进行取模,这样卷积序列的每个位置上的数字大小必定不超过$P^2n$。

这样的话,我们可以选择若干能够进行NTT的质数$p_1,p_2,...,p_m$,使得$N=\prod_{i=1}^{m}p_i>P^2n$,我们对于这些质数均进行一次NTT,对于结果再使用CRT合并起来,得到的就是在模$N$意义下的卷积,实际上就是这个卷积本身,再取出每个系数模上$P$就能得到答案了。

只要合理的选择质数就能达到这种效果了。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter