Picks's Blog

Fast Fourier Transform Modulo Prime

| Comments

吐槽

自从发了那篇组合数取模之后,一坨人问我怎么在模任意素数 的情况下进行FFT。
那我就稍微写一下吧……挺没意思的一个东西。

处理方法

首先我们可以显然地处理当 的情况。
那么对于一个 ,我们取 个满足上式的素数 ,对每个素数分别来做FFT,之后再用CRT合并起来。
比如当 级的数的时候,可以取3个设计好的素数进行FFT,然后再用CRT将他们合并。使用wiki上的公式:

可以用int128避免写高精度。
当然,FFT之后常数乘上三,估计也没有什么题能跑过去了……

Comments

comments powered by Disqus