2次元FFT

http://jag2013spring.contest.atcoder.jp/tasks/icpc2013spring_f
を解いたので，2次元FFTのやり方．

1次元FFT

まずは，離散フーリエ変換を．
数列 f(0), f(1), …, f(N-1) に対するフーリエ変換は，
$F(y) = \sum_{0 \leq x < N} f(x)\exp(\frac{2 \pi i}{N}xy).$
※ $\exp$ の中の符号が逆だったりする事も有るけど問題無い．
逆フーリエ変換は，
$f(x) = \frac{1}{N}\sum_{0 \leq y < N} F(y)\exp(-\frac{2 \pi i}{N}xy).$

F(0), F(1), …, F(N-1) をまとめて高速(O(NlogN))に求めることが出来る，というのが高速フーリエ変換(FFT)だった．これは省略．

2次元FFTは，1次元FFTを利用する．
関数f(x, y) (0 <= x < M, 0 <= y < N)に対するフーリエ変換は，
$F(k, l) = \sum_{0 \leq x < M}\sum_{0 \leq y < N}f(x, y)\exp(\frac{2 \pi i}{M}xk)\exp(\frac{2 \pi i}{N}yl).$
逆フーリエ変換は，
$f(x, y) = \frac{1}{MN}\sum_{0 \leq k < M}\sum_{0 \leq l < N}F(k, l)\exp(-\frac{2 \pi i}{M}xk)\exp(-\frac{2 \pi i}{N}yl).$

フーリエ変換の式をいじると，
$F(k, l) = \sum_{0 \leq y < N}\left[ \sum_{0 \leq x < M}f(x, y)\exp(\frac{2 \pi i}{M}xk) \right] \exp(\frac{2 \pi i}{N}yl)$
となる．これ即ち[・]の内側はFFT．

つまり，各行についてFFTした後に各列にFFTをすればOK．時間計算量はO(MNlogM)．

y(0 <= y < N) について，f(0, y), f(1, y), …, f(M-1, y)をFFTし，g(0, y), g(1, y), …, g(M-1, y)とする．
x(0 <= x < M)について，g(x, 0), g(x, 1), …, g(x, N-1)をFFTし，F(x, 0), F(x, 1), …, F(x, N-1)とする．
f(x, y)の2次元FFT F(k, l)が得られた．

逆2次元FFTは，上記のFFTをそのまま逆FFTにするだけでいい．