今日は行列累乗のお話をしてみます．
先日 はダブリングの話をしましたが，あの方法では，遷移しうる状態すべてを陽に持てる必要があったと思います． たとえば，頂点数 \(10^5\) 程度の木の頂点を「状態」と見なす場合は，持っておくことができるのでダブリングが可能でした．
今回は，それができない場合でも適用できる（可能性のある）方法です．
\(n\) 項めの値を求めたい \(p\) 個の数列 \(a_1, \dots, a_p\) があるとします． つまり，\(a_{1, n}, \dots, a_{p, n}\) を求めたいです．
\(i\) 項めの値 \(a_{1, i}, \dots, a_{p, i}\) がわかっているとき，\(i+1\) 項めの値を求めたいです． これを求めるために，別の \(q\) 個の数列 \(b_1, \dots, b_q\) をうまく定義して，次の条件が満たされるようにできると嬉しいです．
- \(a_{j, i+1}\) は \(a_{1, i}, \dots, a_{p, i}, b_{1, i}, \dots, b_{q, i}\) の線形結合で書ける
- \(b_{j, i+1}\) も \(a_{1, i}, \dots, a_{p, i}, b_{1, i}, \dots, b_{q, i}\) の線形結合で書ける
- これらの線形結合の係数はどんな \(i\) に対しても一定である
すなわち，以下のように書けることになります． \[ \begin{aligned} a_{1, i+1} &= c_{1, 1}\cdot a_{1, i} + \dots + c_{1, p}\cdot a_{p, i} + c_{1, p+1}\cdot b_{1, i} + \dots + c_{1, p+q}\cdot b_{q, i} \\ \vdots\\ a_{p, i+1} &= c_{p, 1}\cdot a_{p, i} + \dots + c_{p, p}\cdot a_{p, i} + c_{p, p+1}\cdot b_{1, i} + \dots + c_{p, p+q}\cdot b_{q, i} \\ b_{1, i+1} &= c_{p+1, 1}\cdot a_{p+1, i} + \dots + c_{p+1, p}\cdot a_{p, i} + c_{p+1, p+1}\cdot b_{1, i} + \dots + c_{p+1, p+q}\cdot b_{q, i} \\ \vdots\\ b_{q, i+1} &= c_{p+q, 1}\cdot a_{1, i} + \dots + c_{p+q, p}\cdot a_{p, i} + c_{p+q, p+1}\cdot b_{1, i} + \dots + c_{p+q, p+q}\cdot b_{q, i} \\ \end{aligned} \]
これはつまり，こうです． \[ \left(\begin{matrix} c_{1, 1} & \dots & c_{1, p} & c_{1, p+1} & \dots & c_{1, p+q} \\ \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ c_{p, 1} & \dots & c_{p, p} & c_{p, p+1} & \dots & c_{p, p+q} \\ c_{p+1, 1} & \dots & c_{p+1, p} & c_{p+1, p+1} & \dots & c_{p+1, p+q} \\ \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ c_{p+q, 1} & \dots & c_{p+q, p} & c_{p+q, p+1} & \dots & c_{p+q, p+q} \end{matrix}\right)\times\left(\begin{matrix} a_{1, i} \\ \vdots \\ a_{p, i} \\ b_{1, i} \\ \vdots \\ b_{q, i} \end{matrix}\right) = \left(\begin{matrix} a_{1, i+1} \\ \vdots \\ a_{p, i+1} \\ b_{1, i+1} \\ \vdots \\ b_{q, i+1} \end{matrix}\right) \]
この \(p+q\) 次の正方行列を \(C\) とおきます． これを求めることができたら，\(C^n \times (a_{1, 0}, \dots, a_{p, 0}, b_{1, 0}, \dots, b_{q, 0})^\top \) を二分累乗法などで計算してあげると，\(a_{1, n}, \dots, a_{p, n}\) を求めることができます．
例題
ABC 129 の F 問題の部分問題です．
初項 \(a\) と公差 \(d>0\) の \(m\) 項の等差数列を考えます．この数列の各項を 10 進法で書いて連結させてできた数字列を 10 進数で書いたときの値を \(\mathrm{mod}. M\) で求めてください．ただし，\(a\) と \(a+(m -1)d\) の 10 進法での桁数は \(k\) 桁とします．
たとえば，\(a=11\)，\(d=2\)，\(m=4\)，\(M = 10^8\) なら \(11131517\) となります．
さっきの説明でいうところの \(a_{1, i}\) を，対象の等差数列を \(i\) 項めまで連結させたものとします． （すなわち，上の例では \(a_{1, 0} = 0\)，\(a_{1, 1} = 11\)，\(a_{1, 2} = 1113\) のようになります．）
また，\(b_{1, i}\) を対象の等差数列の \(i+1\) 項めの値とします． （すなわち，上の例では \(b_{1, 0} = 11\)，\(b_{1, 1} = 13\)，\(b_{1, 2} = 15\) のようになります．）
さらに，定数があると便利なので，\(b_{2, i} = 1\) としておきます．
こうすると，次のような行列を考えるとよいことになります． \[ \left(\begin{matrix} ? & ? & ? \\ ? & ? & ? \\ ? & ? & ? \end{matrix}\right) \times \left(\begin{matrix} a_{1, i} \\ b_{1, i} \\ 1 \end{matrix}\right) = \left(\begin{matrix} a_{1, i+1} \\ b_{1, i+1} \\ 1 \end{matrix}\right) = \left(\begin{matrix} 10^k a_{1, i}+b_{1, i} \\ b_{1, i}+d \\ 1 \end{matrix}\right) \] じーっと見つめるとわかります． \[ \left(\begin{matrix} 10^k & 1 & 0 \\ 0 & 1 & d \\ 0 & 0 & 1 \end{matrix}\right) \] よって，次のものを求めるとよいことになりますね． \[ \left(\begin{matrix} 10^k & 1 & 0 \\ 0 & 1 & d \\ 0 & 0 & 1 \end{matrix}\right)^m \times \left(\begin{matrix} 0 \\ a \\ 1 \end{matrix}\right) \] 適宜 \(M\) で割ったあまりで計算してください．
その他
よくある使い道として，グラフ上で各頂点 \(i\) から出発したときの長さ \(m\) のパスの数え上げなどもありますね．
また，これは整数に限って使える方法ではなく，対象とする集合で，演算 \(\cdot\) と \(+\) がいい感じの性質を満たせばよいです． 結合法則，交換法則，分配法則ができると十分だと思います．
おわり
にゃん
どうやら今週は行列累乗ラッシュだったらしい？
