説明
高速フーリエ変換による任意 mod 畳み込みを行う。
計算量
- $O((n + m) \log (n + m))$
実装例
依存ライブラリ Mod-Int Fast-Fourier-Transform
テンプレート引数としてMod-Intが渡されることを想定している。
- multiply($a$, $b$):= 配列 $a$ と配列 $b$ を畳み込みした結果を返す。
以下は mod $10^9+7$ で verified。ふつうはこっち。
以下は $10^{11}$ 以下の素数 mod で verified。FFT の精度を long double にすること。
検証
AtCoder ATC_001_C 高速フーリエ変換