Relaxed・online convolution

概要

係数が順に確定する因果的畳み込みをblock分割し、確定済みblock間だけをNTTでまとめて更新する。

考え方

時刻nにa_n,b_nが確定し、その直後に c_n=Σ_{i+j=n}a_i b_j を返す問題を考える。未来の係数を必要とする一括NTTは使えない。各積a_i b_jを、二つの係数が確定した後かつc_{i+j}を読む前に、一度だけ予約加算する。

添字平面を長さ2冪のblockへ分ける

L=1,2,4,…について、固定blockを I_L=[L-1,2L-2] とする。添字は両端を含む。相手blockは J_{L,t}=[(t+1)L-1,(t+2)L-2](t≥0)で、t=0ならI_Lと同じである。

各L,tに対して、a[I_L] * b[J_{L,t}] を通常の畳み込みで計算する。t≥1なら a[J_{L,t}] * b[I_L] も計算する。t=0の正方形は一回だけ計算する。

これで全組(i,j)を一意に覆う。実際、min(i,j)が入る区間 [L-1,2L-2] は一つだけで、大きい添字の入るJも一つだけである。両方がIに入るときは正方形、それ以外は大小に応じた一方の長方形へ入る。

発動時刻と出力への配置

Jの右端が確定する n=(t+2)L-2 に積を実行する。二blockとも時刻nまでに確定している。積の最小出力添字も (L-1)+((t+1)L-1)=n なので、出力が必要になる最初の時刻に間に合う。

blockを0始まりの長さL配列へコピーして積dを求め、各q=0,…,2L-2について c[n+q]+=d[q] と予約する。必要精度を超える出力は捨てる。対称な積も同じ出力範囲へ加える。

実装時は、a_n,b_nを追加した直後に、L | (n+2) かつ 2L-2≤n を満たす各2冪Lを走査する。t=(n+2)/L-2 から相手blockが決まる。すべての予約を終えてからc_nを返す。例えばL=2では固定block[1,2]を、時刻2に[1,2]と、時刻4に[3,4]と掛ける。

この分割の不変量は「読んだc_nに寄与する全積は既に一度だけ加算され、以後c_nは変化しない」。一意な被覆が重複・欠落を、最小出力と発動時刻の一致が先読みによる循環を防ぐ。

成立条件と計算量

長さLのblock積はM(L)=O(L log L)、発動はO(N/L)回なので、一段O(N log L)。O(log N)段を合計してO(N log² N)時間、係数列と予約配列はO(N)空間になる。L=1は定数時間で直接掛ける。

a_n,b_nはc_nを返す前に既知でなければならない。次の係数が過去のc_0,…,c_{n-1}に依存する再帰なら使えるが、a_nが未解決のc_nに依存するなら、定数項による同時方程式を先に解く必要がある。このblock配置はABC315 Ex公式解説のオンライン畳み込みにも対応する。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 橙色(2400–2799)。未確定の係数を参照しないblock分割で、オンラインの係数再帰を高速化する。

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

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

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

Relaxed・online convolution

習得する技能

  • 係数が順に確定する因果的畳み込みをblock分割し、確定済みblock間だけをNTTでまとめて更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

前提と範囲

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

直接の前提単元: NTT・FFTで畳み込みと相互相関を求める。

このUnitを直接前提とする単元: なし。

畳み込み・相互相関で得た考え方と実装を再利用し、Relaxed・online convolutionの発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • Relaxed・online convolutionの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠