FFT (NTT) 関連

FFT (NTT) を用いて $O(n^2)$ から $O(n \log{n})$ に高速化できるもの。
基本的に modulo $p$ で計算することを前提とする。
$
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\stirlingfirst}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}}
\newcommand{\stirlingsecond}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}}
\newcommand{\eulerian}[2]{\genfrac{\langle}{\rangle}{0pt}{}{#1}{#2}}
$

FFT (NTT) 関連

Stirling number of the first kind

$$f_n(x) := \prod_{i=0}^{n-1} (x + i) = \sum _{i=0}^{n} \stirlingfirst{n}{i} x^i$$ とおく。このとき、$$f_{2n}(x) = f_n(x) f_n(x+n)$$ が成り立つので、$f_n(x)$ を用いて $f_n(x+n)$ を $O(n \log n)$ を計算できると、全体としても $O(n \log n)$ で計算できる。

$f_n(x+n)$ の展開式は
$$
\begin{align*}
f_n(x + n) &= \sum _{i=0} ^n \stirlingfirst{n}{i} (x + n) ^i \\
& = \sum_{i=0}^n \stirlingfirst{n}{i}
\sum_{j=0}^{i} x^j n^{i-j} \frac{i!}{j!(i-j)!} \\
& = \sum_{j=0}^{n} \frac{x^j}{j!}
\sum_{i=j}^{n} \stirlingfirst{n}{i} i! \cdot \frac{n^{i-j}}{(i-j)!}
\end{align*}
$$
とかける。よって、$\alpha_i := \stirlingfirst{n}{i} i!$, $\beta_i := \frac{n^i}{i!}$ と定め、
$$
\begin{align*}
A &= [\alpha_0, \alpha_1, \ldots, \alpha_n, 0, 0, 0, \ldots, 0] \\
B &= [\beta_0, 0, 0, 0, \ldots, 0, \beta_n, \beta_{n-1}, \ldots, \beta_1]
\end{align*}
$$
を畳み込むと $f_{n}(x+n)$ の係数が得られる。その後、$f_{2n}(x) = f_{n}(x) f_{n}(x+n)$ を畳み込めばよい。どちらの畳み込みも $O(n \log n)$ で行える。

補足

$g(x+m) = \sum _{i=0}^n \frac{c_i}{i!} x^i$ について、$x := x - m $ と書き換えると、$g(x) = \sum _{i=0}^n \frac{c_i}{i!} (x-m)^i$ となることから、$c_i = \frac{d^ig}{dx^i}(m)$ である。

実行時間例

$n$ sec
1,000,000 1.83
2,000,000 4.68
4,000,000 10.8
8,000,000 24.4
16,000,000 52.7
32,000,000 119

Stirling number of the second kind

$$
\stirlingsecond{n}{m}
= \sum_{i=0}^m \frac{i^n}{i!} \frac{(-1)^{m-i}}{(m-i)!}
$$
が成り立つ。よって、$\alpha_i = \frac{i^n}{i!}, \beta_i = \frac{(-1)^i}{i!}$ とおいて、
$$
\begin{align*}
A &= [\alpha_0, \alpha_1, ..., \alpha_n, 0, ..., 0] \\
B &= [\beta_0, \beta_1, ..., \beta_n, 0, ..., 0]
\end{align*}
$$
で畳み込む。

補足

$i^n = d^n \cdot (i/d)^n$ を利用すれば、実際に $i^n$ を計算しなければいけないのは $i$ が素数 の場合だけである。つまり、$i^n$ の列挙は $O(n \log\log{n})$ でできる。

実行時間例

$n$ sec
1,000,000 1.59
2,000,000 3.40
4,000,000 7.33
8,000,000 15.2
16,000,000 34.3
32,000,000 76.6

Eulerian number

$$
\eulerian{n}{m}
= (n + 1)! \sum_{i=0}^{m} (i+1)^n \frac{(-1)^{m-i}}{(m-i)!(n+1-(m-i))!}
$$
が成り立つ。よって、$\alpha_i = (i+1)^n, \beta_i = \frac{(-1)^i}{i!(n+1-i)!}$ とおいて、
$$
\begin{align*}
A &= [\alpha_0, \alpha_1, ..., \alpha_{n-1}, 0, ..., 0] \\
B &= [\beta_0, \beta_1, ..., \beta_{n-1}, 0, ..., 0]
\end{align*}
$$ で畳み込む。

補足

左右対称となるため、実際は $\left\lceil\frac{n+1}{2}\right\rceil$ 個ずつで畳込み、残りを補完すれば十分。

実行時間例

$n$ sec
1,000,000 0.71
2,000,000 1.54
4,000,000 3.28
8,000,000 7.15
16,000,000 15.1
32,000,000 34.0

行列とベクトルの積

http://www.umiacs.umd.edu/~ramani/pubs/tang_pascal_updated.pdf が詳しい。

Fourier 行列、Circulant 行列、Toeplitz 行列、Hankel 行列、下(上)三角 Pascal 行列とベクトルとの積は、$O(n \log{n})$ で計算できる。

実装

NTT は例えば Matters Computational の p540 の ntt_dit4 などを用いることができる。ntt_dit2 より ntt_dit4 の方が少し早い。

(最近は、FFT を 4 回行って畳み込む実装が多く見られる)

使いやすい素数 ($< 2^{30}$)一覧

周期 $n$ 素数 $p$ (原始根) $z$ ($z^n = 1$) $p-1$ の素因数分解
226 469762049 3 2187 226 * 7
225 167772161 3 243 225 * 5
224 754974721 11 739831874 224 * 32 * 5
223 377487361 7 48510621 223 * 32 * 5
223 595591169 3 361399025 223 * 71
223 645922817 3 224270701 223 * 7 * 11
223 880803841 26 273508579 223 * 3 * 5 * 7
223 897581057 3 872686320 223 * 107
223 998244353 3 15311432 223 * 7 * 17
222 104857601 3 39193363 222 * 52
222 113246209 7 58671006 222 * 33
222 138412033 5 99040867 222 * 3 * 11
222 155189249 6 14921912 222 * 37
222 163577857 23 121532577 222 * 3 * 13
222 230686721 6 71750113 222 * 5 * 11
222 415236097 5 73362476 222 * 32 * 11
222 666894337 5 147340140 222 * 3 * 53
222 683671553 3 236932120 222 * 163
222 918552577 5 86995699 222 * 3 * 73
222 935329793 3 86363943 222 * 223
222 943718401 7 754500478 222 * 32 * 52
222 985661441 3 79986183 222 * 5 * 47
221 111149057 3 60767546 221 * 53
221 132120577 5 102376994 221 * 32 * 7
221 136314881 3 2981173 221 * 5 * 13
221 169869313 5 143354861 221 * 34
221 186646529 3 88383805 221 * 89
221 199229441 3 174670364 221 * 5 * 19
221 211812353 3 113852926 221 * 101
221 249561089 3 61724276 221 * 7 * 17
221 257949697 5 186470816 221 * 3 * 41
221 270532609 22 74891632 221 * 3 * 43
221 274726913 3 255478716 221 * 131
221 383778817 5 324881819 221 * 3 * 61
221 387973121 6 124477810 221 * 5 * 37
221 459276289 11 238723101 221 * 3 * 73
221 463470593 3 428228038 221 * 13 * 17
221 576716801 6 153098993 221 * 52 * 11
221 597688321 11 395834143 221 * 3 * 5 * 19
221 635437057 11 171402456 221 * 3 * 101
221 639631361 6 432237000 221 * 5 * 61
221 648019969 17 592437138 221 * 3 * 103
221 710934529 17 69533131 221 * 3 * 113
221 715128833 3 355872337 221 * 11 * 31
221 740294657 3 237508734 221 * 353
221 786432001 7 228383098 221 * 3 * 53
221 799014913 13 374051146 221 * 3 * 127
221 824180737 5 133412682 221 * 3 * 131
221 899678209 7 118485495 221 * 3 * 11 * 13
221 924844033 5 44009197 221 * 32 * 72
221 950009857 7 741494216 221 * 3 * 151
221 962592769 7 695637473 221 * 33 * 17
221 975175681 17 518451017 221 * 3 * 5 * 31
221 1004535809 3 702606812 221 * 479
221 1012924417 5 673144645 221 * 3 * 7 * 23