固定線形遷移を巨大回数進める

概要

線形遷移・行列累乗

一歩先の各状態が、今の状態の固定された線形和で決まるとき、その更新を行列で表せる。同じ更新を一歩ずつ繰り返す代わりに、2歩・4歩・8歩と進む行列を作り、必要な回数を組み合わせて巨大な時刻まで進める。

考え方

一歩の更新から行列を作る

まず、次の各成分が「更新前のどの成分を何倍して足したものか」を書く。状態数を dd、時刻 tt の状態を列ベクトル vtv_t とし、成分の添字は0始まりとする。行列の成分は T[to][from]、つまり遷移先を行、遷移元を列に置く。

vt+1[i]=∑j=0d−1T[i][j]vt[j],vt+1=Tvt\begin{aligned} v_{t+1}[i]&=\sum_{j=0}^{d-1}T[i][j]v_t[j],\\ v_{t+1}&=Tv_t \end{aligned}

右辺はすべて更新前の値で評価する。一つの配列を順に上書きすると新旧の値が混ざるので、次のベクトルを別に作ってから置き換える。この規約では、行列 AA の更新の後に BB の更新を行う合成は B(Av)=(BA)vB(Av)=(BA)v となる。行ベクトルを使う解説では、行列を転置し、掛ける向きも読み替える。

たとえば ABC293 E の等比和を、小さい例として公比3で考える。最初の tt 項の和を ata_t とすると、

at=∑i=0t−13i,a0=0,at+1=3at+1\begin{aligned} a_t&=\sum_{i=0}^{t-1}3^i,\quad a_0=0,\\ a_{t+1}&=3a_t+1 \end{aligned}

となる。定数項の +1+1 も線形和へ含めるため、常に1の成分を追加する。更新後の第一成分は 3a+1⋅13a+1\cdot1、第二成分は 0⋅a+1⋅1=10\cdot a+1\cdot1=1 なので、

vt=(at1),T=(3101)v_t=\begin{pmatrix}a_t\\1\end{pmatrix},\qquad T=\begin{pmatrix}3&1\\0&1\end{pmatrix}

と書ける。vt+1=Tvtv_{t+1}=Tv_t に従って初期状態から一歩ずつ進むと、

(01)⟶(11)⟶(41)⟶(131)⟶(401)\begin{aligned} \begin{pmatrix}0\\1\end{pmatrix} &\longrightarrow\begin{pmatrix}1\\1\end{pmatrix} \longrightarrow\begin{pmatrix}4\\1\end{pmatrix}\\ &\longrightarrow\begin{pmatrix}13\\1\end{pmatrix} \longrightarrow\begin{pmatrix}40\\1\end{pmatrix} \end{aligned}

となり、一歩後は1、二歩後は4、四歩後は40である。個別公式解説 と同じ構成で、公比を入力値 AA に戻せば左上の3を AA に変えるだけでよい。法 MM での余りを求める場合は各加算・乗算のたびに剰余を取る。除算を使わないので、MM が合成数でも、A−1A-1 の逆元が存在しなくても使える。

二乗で歩幅を倍にし、回数のbitを選ぶ

二歩分は T2=TTT^2=TT、四歩分は T4=T2T2T^4=T^2T^2 として、一つ前の行列を二乗して作れる。先ほどの例では、

T2=(9401),T4=(814001)T^2=\begin{pmatrix}9&4\\0&1\end{pmatrix},\qquad T^4=\begin{pmatrix}81&40\\0&1\end{pmatrix}

であり、どちらも初期ベクトルへ一度掛けるだけで、それぞれ二歩後・四歩後の状態を返す。

求める回数を非負整数 KK とする。たとえば K=13=1+4+8K=13=1+4+8 なら、二進表記は 110121101_2 である。1・2・4・8歩分の行列を作り、bitが立っている1・4・8歩分だけを状態へ適用する。

v0 →T v1 →T4 v5 →T8 v13v_0\ \xrightarrow{T}\ v_1 \ \xrightarrow{T^4}\ v_5 \ \xrightarrow{T^8}\ v_{13}

一般の手順も同じである。

  1. 現在の状態を w=v0w=v_0、現在の歩幅の行列を P=TP=T とする。
  2. KK のbitを下位から調べる。今のbitが1なら、まず w←Pww\leftarrow Pw としてその歩幅を進める。0なら状態は変えない。
  3. 次のbitがあれば、P←PPP\leftarrow PP と二乗して歩幅を倍にし、次のbitへ進む。すべてのbitを処理したら ww が答えの状態である。

最下位を0番目として、jj 番目のbitを処理する直前には、P=T2jP=T^{2^j} であり、ww はそれまでに選んだ歩幅の合計だけ進めた状態になっている。bitが1ならその歩幅を足し、二乗すれば次の歩幅になるため、最後にはちょうど KK 歩進む。各行列が同じ TT の冪なので、この合成で TKv0T^K v_0 を得られる。等比和の例なら、この最終ベクトルの第一成分を取り出す。

K=0K=0 なら一度も更新せず v0v_0 を返す。行列としては T0=IT^0=I、すなわち対角成分が1、他が0の単位行列の作用である。K=1K=1 では一歩の更新だけを行う。

過去の値を状態にする線形漸化式

次数 d≥1d\geq1 の線形漸化式

an=∑j=1dcjan−j(n≥d)a_n=\sum_{j=1}^{d}c_j a_{n-j}\qquad(n\geq d)

でも、次の値に必要な直近の dd 個を状態として残せばよい。係数 c1,…,cdc_1,\ldots,c_d は時刻によらず固定されているとする。

vn=(an,an−1,…,an−d+1)Tv_n=(a_n,a_{n-1},\ldots,a_{n-d+1})^{\mathsf T}

ここで右肩の T\mathsf T は転置を表し、括弧内を列に並べる。新しい第一成分は係数付きの和、残りは以前の値を一つずつ後ろへ移したものなので、遷移行列の第一行は (c1,…,cd)(c_1,\ldots,c_d)、第二行以降は一つ左下の成分だけが1となる。この形の行列をcompanion行列という。d=2d=2 なら具体的に、

(an+1an)=(c1c210)(anan−1)\begin{pmatrix}a_{n+1}\\a_n\end{pmatrix} =\begin{pmatrix}c_1&c_2\\1&0\end{pmatrix} \begin{pmatrix}a_n\\a_{n-1}\end{pmatrix}

である。初期値 a0,…,ad−1a_0,\ldots,a_{d-1} が与えられたとき、初期ベクトルは vd−1v_{d-1}。K≥d−1K\geq d-1 なら TK−(d−1)vd−1T^{K-(d-1)}v_{d-1} の第一成分が aKa_K であり、それより小さい KK は与えられた初期値から直接返す。

特性多項式の剰余で一つの項を求める

漸化式の係数が分かっていて一つの項 aKa_K が欲しいときは、状態を行列で進めるほかに、多項式で計算を圧縮する方法がある。次の多項式をこの漸化式の特性多項式とする。

h(X)=Xd−c1Xd−1−⋯−cdh(X)=X^d-c_1X^{d-1}-\cdots-c_d

XKX^K を h(X)h(X) で割った剰余を

r(X)=XK mod h(X)=∑i=0d−1riXir(X)=X^K\bmod h(X)=\sum_{i=0}^{d-1}r_iX^i

とおくと、答えは初期値の線形和になる。

aK=∑i=0d−1riaia_K=\sum_{i=0}^{d-1}r_i a_i

この理由を確認する。任意の非負整数 ss について、Xsh(X)X^s h(X) の各 XiX^i を aia_i に置き換えて係数付きで足すと、

as+d−∑j=1dcjas+d−j=0a_{s+d}-\sum_{j=1}^{d}c_j a_{s+d-j}=0

となる。したがって、これらの線形結合である h(X)h(X) の任意の多項式倍も、同じ置き換えで0になる。XK−r(X)X^K-r(X) は h(X)h(X) の倍数なので、aK−∑iriai=0a_K-\sum_i r_i a_i=0 が得られる。

剰余は、行列の代わりに多項式を二分累乗して求める。答え用の多項式を1、現在の冪を X mod h(X)X\bmod h(X) から始め、各bitでの乗算・二乗のたびに h(X)h(X) の剰余へ戻す。次数が dd 未満の多項式同士を掛けた後、次数 m≥dm\geq d の項を高い方から

Xm≡∑j=1dcjXm−j(modh(X))X^m\equiv\sum_{j=1}^{d}c_jX^{m-j}\pmod{h(X)}

で消していけばよい。積と剰余への整理はそれぞれ素朴な実装で O(d2)O(d^2)、最後の初期値との積和は O(d)O(d) で済む。これにより、既知の係数・初期値から K≥1K\geq1 の項を O(d2log⁡(K+1))O(d^2\log(K+1)) 時間、逐次二乗なら O(d)O(d) 空間で求められる。K=0K=0 は初期値をそのまま返す。hh の最高次係数が1なので、この整理にも除算や逆元は不要である。

この高速化は、漸化式を使って保持する量を多項式の係数へ変えた結果である。一般の密行列のまま、掛ける相手をベクトルに変えるだけで同じ全体計算量になるわけではない。

成立条件と計算量

まず、状態を固定すれば同じ線形更新が毎回使えることを確認する。係数が時刻や状態値で変わる場合、一つの固定行列をそのまま累乗することはできない。周期をまとめる、必要な情報を状態へ加えるなどの再定式化が必要になる。

ABC258 Ex のように、通常の遷移が続く巨大な区間の間に少数の禁止位置がある場合は、同じ遷移が続く区間だけを累乗で飛ばす。例外位置では別の更新を行い、次の固定区間へ進む。異なる行列を含むので、列ベクトルなら後の更新を左へ掛ける順序も守る。

一般の d×dd\times d 密行列を素朴に扱う場合、費用は次のように分かれる。各加算・乗算を定数時間と数える。

処理時間
遷移係数を列挙し、密行列へ格納する問題固有の係数計算に加え、格納領域の初期化に O(d2)O(d^2)
T,T2,T4,…T,T^2,T^4,\ldots を二乗で用意する一回 O(d3)O(d^3)、全体で O(d3log⁡(K+1))O(d^3\log(K+1))
bitが1の冪行列を一つの状態ベクトルへ掛ける一回 O(d2)O(d^2)、全体で O(d2log⁡(K+1))O(d^2\log(K+1))

K≥1K\geq1 では、行列を用意する費用も含めると、問題固有の係数計算に加えて全体で O(d3log⁡(K+1))O(d^3\log(K+1)) 時間となる。O(d2log⁡(K+1))O(d^2\log(K+1)) は、必要な冪行列がすでにある場合に、一つの初期ベクトルを進める費用だけである。元の行列が疎でも、二乗した行列まで疎とは限らない。

すべての冪行列を保存すれば、K≥1K\geq1 で O(d2log⁡(K+1))O(d^2\log(K+1)) 空間を使い、同じ遷移を使う別の初期ベクトルにも再利用できる。一つのベクトルだけを進めるなら、その場で二乗しながら適用して古い行列を捨てればよい。現在の行列・積の作業領域・状態ベクトルだけなので、追加空間は O(d2)O(d^2) で済む。K=0K=0 なら行列の構築や二乗は不要で、初期ベクトルを返すだけである。

既知の線形漸化式に対する特性多項式剰余法は、上で導いた別の選択肢である。漸化式の係数を求める処理が別途必要なら、その前処理も加える。問題に応じて「何を一歩とするか」「何回進むか」「最終状態のどの成分・成分和が答えか」を決めてから、状態数と前処理を含めた費用を見積もる。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 青色(1600–1999)。固定線形遷移を行列や漸化式へ写し、巨大回数の反復を二分累乗する。

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

概念上の親: 動的計画法。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-linear-recurrence

習得する技能

  • 固定線形遷移を行列または漸化式にし、巨大回数後の値を求められる。

前提と範囲

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

直接の前提単元: 最小十分状態からDPを設計する。

このUnitを直接前提とする単元: 半環行列・min-plus/max-min遷移。

一回分の状態遷移を表せることを前提に、固定線形変換を累乗して巨大回数後へ進める。

このUnitでは扱わないもの

  • 一般のDP遷移の区間集約・単調最適化。

根拠