はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるFFT問題まとめ

FFT : Fast Fourier Transform

  • 高速フーリエ変換
  • 畳み込みというのを高速化する手法
  • C[k] = sum{i=0...k}A[i]*B[k-i]を高速化する(O(NlogN))
  • 流れ

1. 配列A,Bを高速フーリエ変換する
2. 配列CをC[i] = A[i] * B[i]で作る
3. 配列Cを逆高速フーリエ変換すると答え

  • 二次元FFTというのもある
  • 組合せ問題を解くのにFFTを使ったりする

多項式を使って組合せを求める例

  • 神「ビットマスクの掛け合わせを行う問題はFFTかも」
  • FFTでもしTLEしてしまう場合はdouble計算をfloatにするテクがある(1.5倍くらい早くなるが、誤差ミスが起こる可能性があるこの問題では誤差WAした)
  • FFTでは総じてTLEが厳しいので、注意して実装しよう

【発展的話題】 NTT