通常の畳み込み（高速版）

convolution/convolution.hpp · GitHub で見る

全体サイト（256 KiB向け） · 高速実装

軽量実装（64 KiB）はこちら

#include "lib/convolution/convolution.hpp"

std::vector<mint> a{1, 2, 3}, b{4, 5};
auto c = convolution(a, b); // {4,13,22,15}

操作	内容・返り値	計算量
convolution(a,b)	通常の畳み込み \(\displaystyle c_k=\sum_{i+j=k}a_ib_j\) を返す。係数型から実装を選ぶ	NTT・CRT・FFT: \(O(L\log L)\)、一般の環: \(O(L^{\log_2 3})\)

\(\displaystyle c_k = \sum_{i+j=k} a_i b_j\) を返します。

配列は定数項から順に多項式の係数を並べます。例は \((1+2x+3x^2)(4+5x)\) の係数です。返り値は入力と同じ係数型の vector で、両方が非空なら長さは a.size()+b.size()-1、どちらかが空なら空配列です。入力は変更しません。mint の結果を整数に直すには c[i].val() を使います。

係数型	実装・条件
mint・mod 998244353 の modint	既存 FPS の NTT。出力長 \(\le 2^{23}\)
その他の modint	32 bit 以下の mod。mod()・val()・raw() が必要。出力長 \(\le 2^{24}\)
64 bit 以下の整数	CRT による厳密計算。結果が係数型に収まること。出力長 \(\le 2^{24}\)
浮動小数点・std::complex	FFT による近似計算
その他の環	Karatsuba。T(0)・+=・-=・* が必要

各種畳み込みの参考記事。添字・集約・要素同士の演算は各ヘッダーの説明に記載しています。

\(L = \lvert a\rvert + \lvert b\rvert\) として、NTT・CRT・FFT は時間 \(O(L \log L)\)、その他の環は \(O(L^{\log_2 3})\)、追加空間はいずれも \(O(L)\) です。

依存ライブラリ

• 畳み込みの型別振り分け
• FFT
• FPS のブロック変換
• FPS の融合畳み込み
• FPS の定数係数畳み込み
• FPS の非対称畳み込み
• FPS と多項式除算の内部変換
• FPS の指数・冪の内部変換
• FPS の一点評価
• FPS 逆数のブロック変換
• FPS の内部演算
• FPS の結果配列への一括変換
• 疎 FPS の共通演算
• 疎 FPS の次数圧縮・前処理
• 疎 FPS の項収集・演算種別
• FPS 平方根のブロック変換
• FPS の作業領域
• modint998244353 の共通剰余演算
• modint998244353 の共有畳み込み
• NTT（998244353）（高速版）
• NTT（法指定）
• 実数・複素数の畳み込み
• 任意 mod・整数の畳み込み
• 一般の環の畳み込み
• 形式的冪級数（高速版）
• modint998244353

検証コード

• test/convolution.test.cpp

コード

#ifndef CONVOLUTION_HPP
#define CONVOLUTION_HPP

#include "../fps/fps.hpp"
#include "../components/convolution_dispatch.hpp"

#endif

Back to top page