概要
2025年7月中旬頃から，えこってさん（https://x.com/eco4kb, https://atcoder.jp/users/ecottea）によって，あるタイプの dp の出力を推定する研究がされています．
この研究により，高難易度のものを含むいくつかの問題が AC 可能であることも報告されています．一方で，後述の定式化のような行列によって記述できる解法があるという仮定のもとであっても，えこってさんの手法の正当性は今のところ証明されていませんでした．
本記事では，問題の定式化と手法の概要について簡単に解説し，さらに手法の正当性について証明します．問題の定式化と手法の概要についてはえこってさんのオリジナルのものであり，正当性の証明についてはこの記事が初出の結果だと思います．
簡易版：BMBM法
モチベーションの説明のために，はじめに簡易版の問題について述べます．この内容は競技プログラミングでも広く知られており，既知の読者も多いと思います．
次の問題を考えます．
【問題】$d$ が既知であり，未知の $d\times d$ 行列 $A$ および，$1\times d$ 行列 $u$，$d\times 1$ 行列 $v$ があるとする．数列 $\{a_i\}$ を $a_i=uA^iv$ で定める．
十分小さな場合の $a_i$ の値 $a_0,a_1,\ldots,a_m$ が既知であるとする．$n$ を入力として $a_n$ を求めよ．
（入力イメージ）$d=2$, $a_0=0,a_1=1,a_2=1,a_3=2,a_4=3,a_5=5$. $a_{10}=?$
（出力イメージ）$a_{10}=55$
まず $a_i=uA^iv$ という式について説明します．これは典型的な dp の形のひとつです．
- 初期状態のベクトル $v$ がある（$d$ 状態ごとの初期値がある）．
- $A$ が dp 遷移を表す行列（$d$ 状態から $d$ 状態へのそれぞれに適当な係数で足される）．
- 最後に $u$ をかける．これは $i$ 回の dp 遷移の後にベクトルの成分の適当な線形結合を答えとして出力することを表す．
この【問題】は有名問題で，$m\geq 2d$ であるときに $O(d\log d(\log d+\log n))$ 時間で答を求めることができます．
まず行列 $A$ とベクトル $v$ について，$A^dv=\sum_{j=1}^dc_jA^{d-j}v$ の形の関係式が存在します．このことは $d+1$ 個のベクトル $(A^iv)_{0\leq i\leq d}$ が線形従属であることから示すことができます．あるいは Cayley Hamilton の定理からも同じことが分かります．
このことから，$\{a_i\}$ は次の形の線形漸化式を持つことが分かります：$a_i=\sum_{j=1}^d c_ja_{i-j}$．
$m\geq 2d$ のもとで，Berlekamp-Massey のアルゴリズムによって，このような漸化式のひとつを $O(d\log^2 d)$ 時間で得ることができます．（「漸化式のひとつ」と書いたのは，同じ数列でも複数の漸化式が考えられるからです．例えば $a_i=2^i$ という数列は $a_i=2a_{i-1}$, $a_i=a_{i-1}+2a_{i-2}$, $a_i=4a_{i-2}$ などを満たします．Berlekamp-Massey のアルゴリズムはそのようなもののうちで $d$ が最小のものを出力します）．
$\{a_i\}$ が満たす漸化式が分かると，$a_n$ は Bostan-Mori のアルゴリズムによって $O(d\log d(\log d+\log n))$ 時間で求めることができます．
日本の競技プログラミングでは Berlekamp-Massey, Bostan-Mori を用いる一連の流れをまとめて BMBM 法とも呼ばれているようです．
- Library Checker 「Find Linear Recurrence」：https://judge.yosupo.jp/problem/find_linear_recurrence
- Library Checker 「Kth term of Linearly Recurrent Sequence」：https://judge.yosupo.jp/problem/kth_term_of_linearly_recurrent_sequence
この手法により，いわゆる行列累乗で解ける問題の多くを，行列を持ち出すことなく（場合によってはより良い計算量で）解くことが可能になります．行列が存在することまでは証明できているものの，実際に行列を書き下すのは小さい場合の値を計算することに比べて難しいということは珍しくないので，実用度は高いです．dp 遷移を行列に書き直すのに苦労したことがある人にはその便利さが想像できるかもしれません．
この手法は，解法の正当性を確認しないまま AC を得ることを狙う手段として使われることもあります．
一方でそのような手段に否定的なプレイヤにとっても，dp が行列で書けることまで証明できていれば正当性の保証がされている解法となるため，支持されていると思います．
えこってさんの「文字列 dp 問題」
BMBM 法は，あるひとつの行列による dp 遷移が反復される場合に適用可能でした．これを複数種類の行列による遷移の場合に拡張しようというのがえこってさんの研究（のひとつ）です．
簡単のため A, B, C からなる文字列の場合に述べます．
【問題】$d$ が既知であり，未知の $d\times d$ 行列 $A, B, C$ および，$1\times d$ 行列 $u$，$d\times 1$ 行列 $v$ があるとする．A, B, C からなる文字列 $S$ に対して $uSv$ を $S$ を対応する行列積に置換して得られる値であるとする．（例えば $S$ が “ABCAA” のとき $uSv=uABCAAv$ とする．）
十分短いすべての $S$ に対する $uSv$ を既知とするとき，任意の文字列 $S$ に対する $uSv$ を計算せよ．
このことに対するえこってさんの手法の正当性を証明することが本記事の主目標です．上の状況（未知の行列の存在）を前提とします．
以下，$f(S)=uSv$ と書くことにします．
【定理 1】文字列からなる集合 $\mathcal{T}=\{T_0,T_1,\ldots\}$ であって，以下の条件をすべて満たすものが存在する．
- $\mathcal{T}$ は長さ $d-1$ 以下の文字列からなる．
- $|\mathcal{T}|\leq d$
- 任意の長さ $d$ 以下の文字列 $S$ に対して，ある係数列 $(c^S_i)_i$ であって $Sv=\sum_i c^S_iT_iv$ を満たすものが存在する．
【証明】非負整数 $i$ に対してベクトル空間 $V_i$ を $V_i = \mathrm{span}(\{Sv\mid |S|\leq i\})$ と定めます．例えば $V_2$ は $v, Av, Bv, Cv, AAv, ABv, ACv, BAv, BBv, BCv, CAv, CBv, CCv$ によって生成されるベクトル空間です．
これらは次を満たします：$V_{i+1}=V_i+AV_i+BV_i+CV_i$．したがってある $k$ が存在して，$V_0\subsetneq V_1\subsetneq \cdots \subsetneq V_k=V_{k+1}=V_{k+2}=\cdots$ が成り立ちます．$\dim V_k\leq d$ より $k\leq d-1$ で，（$\dim V_0$ が $0,1$ のどちらであるかの簡単な場合分けによって）$V_{d-1}=V_d=V_{d+1}=\cdots$ が分かります．
$\dim V_{d-1}\leq d$ なので $V_{d-1}$ は $d$ 個以下の $Tv$ （$|T|\leq d-1$）によって生成されます．それらを $\mathcal{T}$ とすれば定理が成り立ちます．
定理のような $\mathcal{T}$ や $c^S_i$ の存在は証明されたものの，実際には行列 $A,B,C,v$ は未知であり，これらを計算する方法はありません．$f(S)=uSv$ の値だけが得られる今の問題設定に利用可能な形で述べなおします．
【定理 2】文字列からなる集合 $\mathcal{T}=\{T_0,T_1,\ldots\}$ および，各長さ $d$ 以下の文字列 $S$ に対する係数列 $(c^S_i)_i$ であって，以下を満たすものが存在する．
- $\mathcal{T}$ は長さ $d-1$ 以下の文字列からなる．
- $|\mathcal{T}|\leq d$
- 任意の文字列 $X$ に対して $f(XS)=\sum_i c^S_if(XT_i)$．
【定理 1】より明らかです．
この条件を満たすデータを見つけるというのがえこってさんのアイデアです．まずはその存在は証明できたことになります．
一方でこのままでは，見つけたデータの正しさを確かめる方法がありません．十分短い $S$ に対する $f(S)$ しか得られない状況なので，特に「任意の文字列 $X$ に対して」という部分が問題です．次にこの部分を解決します．
【定理 3】$w$ を $d\times 1$ 行列とするとき，次は同値である．
(1) 任意の文字列 $X$ に対して $uXw=0$．
(2) 任意の長さ $d-1$ 以下の文字列 $X$ に対して $uXw=0$．
【証明】証明はほとんど【定理 1】と同じです．整数 $i$ に対してベクトル空間 $W_i$ を $W_i = \mathrm{span}(\{Sw\mid |S|\leq i\})$ と定めます．
(1) は任意の $i$ について $uW_i=0$ ということであり，(2) は $uW_{d-1}=0$ ということです．あとは【定理 1】で示したように $W_{d-1}=W_d=W_{d+1}=\cdots$ となることから明らかです．
以上をまとめて次の結論を得ます．
【定理 4】【問題】の状況で
- 長さ $d-1$ 以下の文字列集合 $\mathcal{T}=\{T_0,\ldots,T_{m-1}\}$ ($m\leq d$)．
- 長さ $d$ 以下の各文字列 $S$ に対する係数列 $(c^S_i)_{0\leq i<m}$．
の組 $(\mathcal{T},(c^S_i)_{S,i})$ であって，次の条件を満たすものが存在する．
- 任意の長さ $d$ 以下の文字列 $S$ および長さ $d-1$ 以下の文字列 $X$ に対して $f(XS)=\sum_i c^S_if(XT_i)$．
さらにこのような組に対して次が成り立つ．
- 任意の長さ $d$ 以下の文字列 $S$ および文字列 $X$ に対して $f(XS)=\sum_i c^S_if(XT_i)$．
【証明】存在は【定理 2】で示されている．最後の条件を示せばよい．
$w=Sv-\sum_ic^S_i T_iv$ とすると，示すべきは $uXw=0$ ということになる．【定理 3】より，この等式は長さ $d-1$ 以下の $X$ で成り立てば任意の $X$ で成り立つのでよい．
【定理 4】より，【問題】について例えば次のような解法が可能だということになります．
- 【定理 4】を満たすデータ $\mathcal{T}$, $(C^S_i)$ を見つける．これは長さ $2d-1$ 以下の $S$ に対する $f(S)$ の値をすべて何らかの手段（愚直な全探索など）で求めておくと，単純な連立 $1$ 次方程式の問題として解くことができる．
- このようなデータが計算されているとき，組 $(f(ST_i))_i$ を考えると，$S$ の末尾に $1$ 文字追加したときの変化を表す行列を求めることができます．特に $T_0$ を空文字列にとる（これは上の証明から可能だと分かる）ことで，$f(S)=uSv$ となる行列 $A,B,C,u,v$ のひとつを求めることもできます．
- 特に適切な前計算のもと，$f(S)$ の計算は $O(d^2|S|)$ 時間で行うことができます．
これがえこってさんの手法であり，本記事によってその正当性が理論的に保証できたことになります．ただし，私は手法の詳細は把握していないので，特に最後に述べた解法部分は細かい部分で差があると思います．
具体的な実装方法，適用範囲，さらなる一般化や高速化について本記事では解説しないので，えこってさんのツイートを参考にしてください．
