NTT・FFTで畳み込みと相互相関を求める

概要

畳み込み・相互相関

係数積和または反転列とのcorrelationを多項式積へ写し、必要な次数範囲をNTT/FFTで計算する。

ABC291 Gの巡回shiftごとのbitwise ORの総和を考える。観察: a_i,b_iをそのbitが0である指示変数とする。shift sでORが0の個数はR_s=Σ_{i=0}^{N-1}a_{(i+s) mod N}b_i。全shiftを直接計算するとO(N²)。

変換: aを2周並べてu、bを反転してv_j=b_{N-1-j}とする。多項式U(x)V(x)の係数c_tはΣ_{p+q=t}u_pv_q。t=N-1+sならp=i+s,q=N-1-iとなり、c_{N-1+s}=R_sを得る。

出力: 各bitの寄与は2^bit·(N-R_s)。5 bitの寄与をshiftごとに足してから最大化する。bitごとに最適shiftを選ぶことはできない。

計算量と境界: 5回の通常畳み込みでO(N log N)。各係数はN以下なので法998244353で正確に復元できる。N=1とs=N-1で反転位置と参照係数を手計算する。

ABC265 Exは通常の畳み込みだけの導入には用いない。Conwayの数ゲーム、Grundy数、XOR畳み込みを学んだ後に、整数和とXORという異なる合成則を同時に保持する複合問題として取り組む。

考え方

c_k=Σ_{i+j=k}a_i b_jは二つの選択のサイズ和を集約する。多項式の評価点で積を取って逆変換するFFT・NTTにより、全係数の直積を高速に共有する。

成立条件と計算量

変換を逆に戻せる根を選ぶ

素数法p上でradix-2 NTTを使うとき、空でない配列a,bに対して変換長Lを次の条件で選ぶ。ACL公式仕様にも法と長さの制約が明記されている。

  • L=2^kで、L≥len(a)+len(b)−1。両配列を長さLまで0で埋める。
  • Lがp−1を割り、根ωの位数がちょうどLである。

法pの乗法群の原始根gからω=g^((p−1)/L)を作れば、ord(ω)=Lになる。評価点1,ω,…,ω^(L−1)は相異なり、変換はÂ_j=Σ_{i=0}^{L-1}a_iω^(ij)。評価値同士を掛けたĈ_j=Â_j B̂_jから、c_i=L^(-1)Σ_{j=0}^{L-1}Ĉ_jω^(-ij)で戻す。逆変換ではωの逆元とLの逆元を使う。Lはp−1の約数なのでpでは0にならない。

位数がLを割るだけでは足りない。法17、L=4でω=−1を使うと評価点は1,−1,1,−1となり、非零多項式1−x²さえ全点で0になる。長さ条件にも意味がある。NTTで得るのはmod (x^L−1)の積なので、Lが足りなければ高次係数が低次へ折り返して通常の畳み込みとは異なる。

例えば998244353=119·2^23+1ではg=3を使え、2冪の変換長は2^23まで取れる。計算量はO(L log L)、領域はO(L)。相関への変換で片側を反転する操作は、根・長さの選択とは別に添字を確認する。

NTTの答えは法pでの係数である。整数の係数をそのまま復元するには値域が必要で、非負係数なら全係数がp未満であることを保証する。複数の法からCRTで復元して任意の法へ移す場合も、その積で整数係数を一意に決められる範囲が必要。実数・複素数上のFFTでは同じ変換構造を使えるが、整数への丸めには誤差評価が別途必要となる。

下位単元

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 黄色(2000–2399)。係数積和へ還元し、NTT・FFTの法・長さ・次数の条件を理解して利用する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 組合せ・多項式・線形代数。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-polynomial-convolution

習得する技能

  • 係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: FPS基本演算と多項式の多点評価を行う、heavy path上の多項式木DP、factorial convolutionによる多項式Taylor shift、Relaxed・online convolution。

係数積和を多項式積へ写し、NTT・FFTで畳み込みや反転した列との相互相関を高速に求める。

このUnitでは扱わないもの

  • 組合せ解釈を必要とする生成関数の設計、および逆数・対数・指数などのFPS演算。

根拠