convolution

高速フーリエ変換(FFT)を使って畳み込みを高速で計算することが出来ます。

初期化

CONV=FFT(mod)

modには素数が入ります。ただしどんな素数でもOKというわけではなく、 「(mod-1)が2でたくさん割れるような素数」が好まれて使われます。 例えばmodの例として有名なのは998244353です。

998244353=119 * 2^23 + 1と書けるため、この素数はFFTに適しています。 2で23回割り切れるため、この場合はAとBの畳み込みを計算するときに、リストの大きさがlen(A)+len(B)-1<=2^23以内ならば畳み込みを正常に計算することが出来ます。

より踏み込んだ説明：普通の高速フーリエ変換では、1の原始2^n乗根を使います。numpyでのフーリエ変換では複素数における原始2^n乗根を用いているのですが、このライブラリではmodの世界における2^n乗根（つまり、x^(2^n) mod p =1,x^k mod p!=1(1<=k<2^n)となるようなx）を使おうとしています。複素数上の演算では浮動小数点を使っていますが、modの世界だと誤差がないというメリットがあります。ここで、原始2^n乗根が存在するような法pというのは、(p-1)が2^nで割り切れることが要求されます。（群論の言葉で書くと、Z/pZの乗法群がZ/(p-1)Zに同型なので、それに位数2^nの元があるためには、p-1が2^nで割り切れればいいという話です。）また、このような「都合のいい素数」は、算術級数定理により存在することが保証されています。

例えば以下のように書きます

CONV=FFT(998244353)

使用例

( https://atcoder.jp/contests/practice2/tasks/practice2_f )

class FFT():
    # (中略)
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
CONV=FFT(998244353)
print(*CONV.convolution(A,B))

任意modのconvolution

10^9+7という素数は、10^9+6が2で1回しか割り切れないため、FFTをするには向いていません。 そのような素数に対してFFTをするためには、「FFTに適している素数」を複数回使ってFFTしたあと、中国剰余定理で復元するのがよいでしょう。実装例は以下のリンクです。

https://judge.yosupo.jp/submission/46207 https://judge.yosupo.jp/submission/126012

同様に2という素数も、2-1が2で0回しか割れないため、FFTをするには向いていません。 mod 2でFFTしたい場合、mod 998244353でFFTした後、最終結果をmod 2にして計算するのが良いでしょう。