2017-12-24

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

この記事は 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)$ のアルゴリズムになります。

2016-08-15

ARC 059 F バイナリハックについて

まーすさんのブログにいちゃもんを付けたら（ごめんなさい）おもしろい話になったので反省も兼ねてブログにメモします。

この問題のsが空文字列である場合の答えa_Nがどんな数列になるかという話をしていました。

arc059.contest.atcoder.jp

つまりこれの途中で出てきたけど結局使わなかったやつです。

dpをするとどうなるか

まず、キーを押す操作を逆から考えます。こうすると、削除は何回でもできるけど入力は今までに削除した回数以上はできないというルールになります。

i回入力してj回削除をする方法の数をi行j列に書いたdpテーブルを考えます。左上に1を書いてから、上の数の2倍+左の数をどんどん書いていけばok

f:id:nuip:20160815210848j:plain

この表でn回キーを押した状態は斜めに並んでいます。なので、求める数はこの表を斜めに足し上げた数です（赤で書いてあるやつ）。この数列はOEISすると出てきます。

https://oeis.org/A126087

漸化式

この数列をよく見ると、nが奇数の時a_{n+1}=a_nになってます。なぜそうなるのかを考えてみると、

f:id:nuip:20160815210856j:plain

こんな感じで、それぞれの数について左側に普通に足したものと、下に2倍して足したものが足されるからだと分かります。だからnが奇数ならこれは絶対成り立ちます。つまり、a_{2n}=3a{2n-1}です。

偶数の時はどうかというと、左下の数の下に数字を書くことが無い（入力する数の方が多くなるから）ため、この法則が成り立ちません。3倍しただけだと、左下の数の2倍だけ本来の数よりも大きくなってしまうので、その分を引いてやる必要が出てきます。

左下の数というのは、削除と入力を同じ回数する場合の数でした。削除の数は入力の数より少なくては行けないので、これは括弧の付け方みたいなもので、ほぼカタラン数です。ぴったりカタラン数ではないのは、この問題では入力の方法が2通りあるからで、入力の数だけ2を掛ければよいです。つまり、合計で2n回キーを押した時の左下は、2^nc_nとなります（c_nはカタラン数のn項目）。つまり、a_{2n+1}=3a_{2n}-2^{n+1}c_nです。

数式をきれいにしたいので後で調べて直します