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公式解説のオンライン畳み込みにも対応する。
問題一覧
- ABC213 H「Stroll」 公式問題組合せ: 再帰分割・分割統治
技能・出典
主題: Relaxed・online convolution(係数が順に確定する因果的畳み込みをblock分割し、確定済みblock間だけをNTTでまとめて更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 再帰分割・分割統治(pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。)。主タグ: Relaxed・online convolution / 補助タグ: 再帰分割・分割統治
- ABC315 Ex「Typical Convolution Problem」 公式問題
技能・出典
主題: Relaxed・online convolution(係数が順に確定する因果的畳み込みをblock分割し、確定済みblock間だけをNTTでまとめて更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。) / 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。)。主タグ: Relaxed・online convolution / 補助タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC230 H「Bullion」 公式問題主題: 母関数方程式・高度な係数抽出
技能・出典
主題: 母関数方程式・高度な係数抽出(母関数の微分恒等式を作り、次数ごとの係数比較から初期値・分母条件を持つ漸化式を導ける。)。追加で学ぶ技能: Relaxed・online convolution(係数が順に確定する因果的畳み込みをblock分割し、確定済みblock間だけをNTTでまとめて更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 再帰分割・分割統治(pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。)。主タグ: 母関数方程式・高度な係数抽出、Relaxed・online convolution / 補助タグ: 再帰分割・分割統治
- ABC281 Ex「Alchemy」 公式問題主題: 組合せを生成関数へ符号化する
技能・出典
主題: 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。)。追加で学ぶ技能: Relaxed・online convolution(係数が順に確定する因果的畳み込みをblock分割し、確定済みblock間だけをNTTでまとめて更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。) / 再帰分割・分割統治(pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。)。主タグ: 生成関数による組合せ構造の符号化、Relaxed・online convolution / 補助タグ: 畳み込み・相互相関、再帰分割・分割統治
- ABC357 G「Stair-like Grid」 公式問題
技能・出典
主題: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。)。追加で学ぶ技能: Relaxed・online convolution(係数が順に確定する因果的畳み込みをblock分割し、確定済みblock間だけをNTTでまとめて更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 再帰分割・分割統治(pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 集合上の包除原理、Relaxed・online convolution / 補助タグ: 組合せ係数・数え上げ、再帰分割・分割統治
前提・学習成果・出典
習得対象の目安: 橙色(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の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。