この記事は Competitive Programming Advent Calendar 2017 の24日目の記事です。

はじめに

この記事の内容

この記事では FFT のアルゴリズムの中身は説明しません。

競プロの問題を解く上で知っておくと有利になりそな部分だけ解説します。「2つの配列を畳み込むアルゴリズム」として解釈してると困るかもしれませんという内容です。そう思ってない人には当り前のことしか書いてありません。

畳み込みとは

数列 $a_0,a_1, a_2, \dots, a_n$ と $b_0,b_1, b_2, \dots, b_n$ に対して、 $c_n= \sum^n_{i=0} a_i b_{n-i}$ で定義される数列 $c_0,c_1, c_2, \dots, c_{2n}$ を求める操作を畳み込みと呼びます。

それぞれの数列を係数として持つ多項式 $f(x)=a_0+a_1x+a_2x^2+\dots+a_nx^n$ , $g(x)=b_0+b_1x+b_2x^2+\dots+b_nx^n$ , $h(x)=c_0+c_1x+c_2x^2+\dots+c_{2n}x^{2n}$ を考えると、 $f(x)\times g(x)=h(x)$ となっているので、畳み込みのかわりに多項式の積を考えても同じことになります。

準備

突然ですが、昨日僕が出題した問題を解いて下さい（脳内ACでもいいです）。

この問題のミソは、 $n$ 次の多項式の掛け算をするのには $O(n^2)$ かかるけど、例えば $(f\times g)(3)$ だけを求めるだけなら、 $f(3)$ と $g(3)$ を計算して掛け算するだけで求まるという部分です。

多項式の掛け算

多項式補間 (interpolation)

ところでこの問題を知っていますか？

ARC033D 見たことのない多項式

ここでは解法には直接言及しませんが、問題文を読むと秘密の $n$ 次多項式 $f(x)$ に対して $n+1$ 点で評価した値 $f(x_0), f(x_1), \dots, f(x_n)$ が分かっていれば、多項式 $f(x)$ が特定できると書いてあります。こういう操作を多項式補間 (interpolation) と言います。

多項式の掛け算のアルゴリズム

多項式補間を使うと、多項式の掛け算を変わった方法で計算することができます。

$n$ 次以下の多項式 $f(x),g(x)$ について、 $f(x)\times g(x)$ を計算するには、

$f(0),f(1),\dots,f(2n)$ を求める（ $O(n^2)$ ）
$g(0),g(1),\dots,g(2n)$ を求める（ $O(n^2)$ ）
$f(0)\times g(0),f(1)\times g(1),\dots,f(2n)\times g(2n)$ を計算する（ $O(n)$ ）
3 で求めた値で多項式補間して $(f\times g)(x)$ を求める（ $O(n^2)$ ）

これは全体でO(n^2)です。普通の掛け算の計算方法と同じですね。

1,2 番目の処理を multi-point evaluation と呼びます。日本語でなんて呼ばれているのかは知りません。誰か教えてください。

FFT

今まで多項式を評価する値は $0,1,\dots,n$ に固定していましたが、実はこれらは $n+1$ 個の異なる値であればなんでも多項式補間できます。

多項式の掛け算をするという目的で多項式補間をする場合、これらの値として何を使うかは本当になんでもいいわけですが、実は特別な値を使うと、multi-point evaluation も多項式補間も $O(n \mathrm{~log~} n)$ で計算できます。これが FFT です。さっきの多項式の掛け算のアルゴリズムが $O(n^2)$ だったのはmulti-point evaluation と多項式補間のせいだったので、そこを FFT で置き換えるだけで多項式の掛け算を $O(n \mathrm{~log~}n)$ で行うことができます。

FFTの解説は別の何か（ATC001Cとか）を読んで下さい。

畳み込み以外

FFTをしたあとの要素ごとに積を取る操作を和に置き換えると、数列の畳み込みでなく数列の和を求めることができます（詳しくはyukicoderに出した問題を参照して下さい。）。例えば、3つの多項式 $f(x),g(x),h(x),i(x)$ に対して $3f(x)(g(x) + 2h(x))i(x)$ を計算するのも、多項式それぞれを1回ずつFFTすれば計算できます。

おまけ

他の変換

上記の1-4のうち、1,2,4を別の変換や逆変換に置き換えると別の操作を $O(n \mathrm{~log~} n)$ のアルゴリズムになります。

もう更新しません

FFT で高速に畳込みを計算する