Last updated:2018-04-06 03:06:02
Category:数学, Tag: FFT


概要


整数列$a$,$b$について,法$p$の下で$a$,$b$を畳み込んで次の列$c$を作る:

\[c_k \equiv \sum_{i=0}^k a_i b_{k-i} \pmod{p}\]

計算量


$N$を$\max(|a|, |b|)$より大きい$2$ベキの数として,$O(N\log N)$.
ただし,以下のNTT_CONVOLUTION_TIMEの値によって定数倍の差があるため注意.

使い方


まず,$m_a:=\max(a), m_b:=\max(b), n:=\min(|a|, |b|)$として,
$X:=m_a m_b n$を求める.($X$は畳み込んで出来る列$c$の要素の最大値)

そして,NTT_CONVOLUTION_TIMEの値を次のように定める:

\[{\tt NTT\_CONVOLUTION\_TIME} = \begin{cases} 1 & (X < 1.2\times 10^9 \sim 2^{30}) \\ 2 & (X < 5.8\times 10^{17} \sim 2^{59}) \\ 3 & (X < 9.7\times 10^{25} \sim 2^{86}) \end{cases}\]
// 例:取り扱う整数がかなり小さいため1でよい
constexpr int NTT_CONVOLUTION_TIME = 1; // namespace NTT内

// ~~~ 以下, 実際に使うところで ~~~

// 列a, bを用意
std::vector<int> a, b;

// a,bを法modで畳み込んだ結果をcとする
std::vector<int> c(NTT::mul(a, b, mod));


そもそもMODを取る必要が無いときは,法$p$を$X+1$などとすれば良い.

// a[i],b[i] <= 100, min(|a|,|b|) <= 100000 より X:=100*100*100000=1000000000
std::vector<int> c(NTT::mul(a, b, 1000000001));

実装例


以下は非再帰,not-in-placeの実装.

問題例


参考文献