行列累乗まとめ

行列累乗の原理と例をひたすら列挙

この記事はZennに投稿したものと同じです.

これはなに

 行列累乗と呼ばれる競プロのテクニックの概要と,それを用いる例をひたすら挙げていきます.競プロチックな話題ではありますが,行列が役立つ場面の例の紹介として,非競プロerでも楽しめると思います.ただし,数列と行列に関する用語がある程度わかっている人向けです.

なお,この記事は長野高専 Advent Calender 2022の2日目の記事です。

原理(フィボナッチ数列の例)

次の式で表される数列を考えます.

F1=1F2=1Fn=Fn1+Fn2 (n3) \begin{align} F_1 &= 1 \\ F_2 &= 1 \\ F_n &= F_{n-1} + F_{n-2} \quad (n \geq 3) \end{align}

これはフィボナッチ数列という名で知られている,F=(1,1,2,3,5,8,13,21,34,)F=(1,1,2,3,5,8,13,21,34,\cdots)という前の22項の和が次の項になる数列です.これの第nn項目をプログラミングで求めることにします.第11項目から第nn項目までを求めるのではなく,第nn項目のみ求めれば良いことに注意です.それっぽいコードを次に示します.

1
2
3
4
5
6
//F[i]:=フィボナッチ数列のi項目
F[1] = 1;
F[2] = 1;
for(int i=3;i<=n;i++){
	F[i] = F[i-1] + F[i-2];
}

for文をnn回くらい回すので計算量はO(n)O(n)です(計算量についてこちら1を参照してください).

では,n=1015n=10^{15}項目を求めたい場合はどうでしょうか.このコードでは,実行が終わりません.

行列で表現する

 ここで,行列です.フィボナッチ数列の定義より,次の式は成り立ちます.

(FnFn1)=(1110)(Fn1Fn2) \begin{pmatrix} F_{n} \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n-1} \\ F_{n-2} \end{pmatrix}

具体的に計算してみます.

(21)=(1110)(11) \begin{pmatrix} 2 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 \\ 1 \end{pmatrix}

(32)=(1110)(21) \begin{pmatrix} 3 \\ 2 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 2 \\ 1 \end{pmatrix}

(53)=(1110)(32) \begin{pmatrix} 5 \\ 3 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 3 \\ 2 \end{pmatrix}

前の22項から次の項が生成されていることがわかりますね. これらの結果を使って次のような変形を考えます.

(53)=(1110)(32)=(1110)(1110)(21)=(1110)(1110)(1110)(11)=(1110)3(11) \begin{align} \begin{pmatrix} 5 \\ 3 \end{pmatrix} &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 3 \\ 2 \end{pmatrix} \\ &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 2 \\ 1 \end{pmatrix} \\ &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 \\ 1 \end{pmatrix} \\ &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} ^3 \begin{pmatrix} 1 \\ 1 \end{pmatrix} \end{align}

始めの22項に同じ行列を33回掛け算することで3つ後の項が出てきました.これを繰り返すと次が成り立つことがわかります.

(FnFn1)=(1110)n2(F2F1) \begin{align} \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} ^{n-2} \begin{pmatrix} F_2 \\ F_1 \end{pmatrix} \end{align}

1010項目を求めたいときは次のように計算できます.

(F10F9)=(1110)8(F2F1)=(89555534)(11)=(14489) \begin{align} \begin{pmatrix} F_{10} \\ F_{9} \end{pmatrix} &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} ^{8} \begin{pmatrix} F_2 \\ F_1 \end{pmatrix} \\ &= \begin{pmatrix} 89 & 55 \\ 55 & 34 \end{pmatrix} \begin{pmatrix} 1 \\ 1 \end{pmatrix} \\ &= \begin{pmatrix} 144 \\ 89 \end{pmatrix} \end{align}

フィボナッチ数列は1,1,2,3,5,8,13,21,34,55,89,144,1,1,2,3,5,8,13,21,34,55,89,144,\cdotsであるため,確かにあっています. 便利そうな式が行列によって完成しました.漸化式の悪いところは前の項の値がわかっていないと次の項が計算できないことですが,この式は特定の項をダイレクトに表すことに成功しています.行列のnn乗が高速に計算できればフィボナッチ数列の第nn項が高速に計算できそうです.

累乗の高速計算

行列AAnn乗であるAnA^nを計算するのに,ナイーブな方法だとn1n-1回の行列同士の掛け算が発生します.この行列同士の掛け算の回数が少なくなることを高速化と呼ぶことにします. A128A^{128}を考えてみましょう.

  • AAAAをかけてA2A^2
  • A2A^2AAをかけてA3A^3 \cdots
  • A127A^{127}AAをかけてA128A^{128}

全部で127127回の掛け算が必要ですね.では,128128という特徴的な数に注目して次のように計算したらどうでしょうか.

  • AAAAをかけてA2A^2
  • A2A^2A2A^2をかけてA4A^4
  • A4A^4A4A^4をかけてA8A^8
  • A8A^{8}A8A^{8}をかけてA16A^{16}
  • A16A^{16}A16A^{16}をかけてA32A^{32}
  • A32A^{32}A32A^{32}をかけてA64A^{64}
  • A64A^{64}A64A^{64}をかけてA128A^{128}

全部で,77回の掛け算でA128A^{128}が計算できました.127127回から77回という驚異の回数削減です. 実は,これは128128のような22の冪数に限った話ではありません.先程,A1,A2,A4,A8,A16,A^1,A^2,A^4,A^8,A^{16},\cdotsを求めましたが,これらを掛け合わせることで任意のAnA^nが計算できます(指数法則AaAb=Aa+bA^aA^b=A^{a+b}が成り立つことに注意).

  • A12=A8A4A^{12} = A^{8} A^{4}
  • A39=A32A4A2A1A^{39} = A^{32} A^{4} A^{2} A^{1}
  • A127=A64A32A16A8A4A2A1A^{127} = A^{64}A^{32}A^{16}A^{8}A^{4}A^{2}A^{1}

これらは,A(2進数表記したとき,1である位)Aの(2進数表記したとき,1である位)乗を掛け算したものになっています. 上の例では,12(10)=1100(2)12_{(10)}=1100_{(2)}であり,11である位は44の位と88の位なので12=8+412=8+4121222の冪数の和で表すことができます. このような手法をダブリングや繰り返し二乗法と呼びます.

それっぽいコードを次に示します.計算量はO(logN)O(\log N)です.O(N)O(N)に比べて非常に高速です2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// AのB乗の計算結果をCの格納
C = I //Iは単位行列
tmp = A
while(B>0){
	if(B%2==1){
		C = C * tmp
	}
	B/=2;
	tmp = tmp * tmp
}

Pythonでの汚い実装例も示します.

愚直パターン
1
2
3
4
5
6
7
8
n = 10000
f = [0]*(n+1)
f[1] = 1
f[2] = 1
for i in range(3, n+1):
    f[i] = f[i-1] + f[i-2]

print(f"第{n}項目は{f[n]}です")
高速化
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def mat_mul(a, b) :
    I, J, K = len(a), len(b[0]), len(b)
    c = [[0] * J for _ in range(I)]
    for i in range(I) :
        for j in range(J) :
            for k in range(K) :
                c[i][j] += a[i][k] * b[k][j]
    return c


def mat_pow(x, n):
    y = [[0] * len(x) for _ in range(len(x))]

    for i in range(len(x)):
        y[i][i] = 1

    while n > 0:
        if n & 1:
            y = mat_mul(x, y)
        x = mat_mul(x, x)
        n //= 2

    return y


ret = [[1],[1]]
mat = [[1,1],[1,0]]
n = 10000
ret = mat_mul(mat_pow(mat, n-2), ret)
print(f"第{n}項目は{ret[0][0]}です")

線形漸化式

フィボナッチ数列は22項間の漸化式でしたが,kk項間の線形漸化式でも可能です.

3項の場合

次で定義される数列aann項目を求めよ.

a1=a2=a3=1an=2an14an2+3an3 (n4) \begin{align} a_1 &= a_2 = a_3 = 1 \\ a_n &= 2a_{n-1} - 4a_{n-2} + 3a_{n-3}\quad (n \geq 4) \end{align}

この漸化式は次のような行列で表されます.

(anan1an2)=(243100010)n3(a3a2a1) \begin{align} \begin{pmatrix} a_n \\ a_{n-1} \\ a_{n-2} \end{pmatrix} &= \begin{pmatrix} 2 & -4 & 3\\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix} ^{n-3} \begin{pmatrix} a_3 \\ a_2 \\ a_1 \end{pmatrix} \end{align}

実際に行列を計算すると確かに成立していることがわかります.

一般に,k+1k+1項間の漸化式はk×kk\times kの行列を使って表され,k×kk\times kの行列同士の掛け算はk3k^3回の掛け算が必要であるため,第nn項を求めるのにO(k3logn)O(k^3\log n)かかります.

なお,k+1k+1項間の線形漸化式の第nn項はkitamasa法と呼ばれる手法で(k2logn)(k^2\log n)で求めることが可能です.こちらもダブリングを使った手法です.

定数項がある場合

a,b,m,x0a,b,m,x_0を使って線形合同法で乱数を生成する.このときのnn番目の乱数xnx_nを求めよ ただし,線形合同法とは,

xi+1=axi+b(modm) x_{i+1} = ax_i + b \pmod m

の漸化式で疑似乱数を生成する手法である.

定数項がある場合は11の行を付け足して次のように作ることができます.

(xn1)=(ab01)n(x01) \begin{align} \begin{pmatrix} x_n \\ 1 \\ \end{pmatrix} &= \begin{pmatrix} a & b\\ 0 & 1 \end{pmatrix} ^{n} \begin{pmatrix} x_0 \\ 1 \end{pmatrix} \end{align}

複数変数の線形漸化式

複数の変数で表される漸化式にも応用できます

平方根を含む数の累乗

次の問題を考えます.

(2+3)n(2+\sqrt{3})^nはいくつか?a+b3a+b\sqrt{3}の形式になるのでa,ba,bを求めよ.

nnが大きいと展開が厄介になりそうなことが想像できますね. とりあえず,2+32+\sqrt{3}の累乗を次のように文字で置きます.

Xn=(an+bn3) X_n = (a_n + b_n\sqrt{3})

XnX_nからXn+1X_{n+1}を計算してみます.

Xn+1=Xn(2+3)=(an+bn3)(2+3)=2an+an3+2bn3+3bn=(2an+3bn)+(an+2bn)3=an+1+bn+13 \begin{align} X_{n+1} &= X_n (2 + \sqrt{3}) \\ &= (a_n + b_n \sqrt{3})(2 + \sqrt{3}) \\ &= 2a_n + a_n \sqrt{3} + 2b_n \sqrt{3} + 3b_n \\ &= (2a_n + 3b_n) + (a_n + 2b_n)\sqrt{3} \\ &= a_{n+1} + b_{n+1} \sqrt{3} \end{align}

最後の二行の係数を比較して,次の漸化式が立ちます.

$$

\begin{align} a_1&=b_1=1 \\ a_{n+1} &= 2a_{n} + 3b_n \\ b_{n+1} &= a_n + 2b_n \end{align}

$$

これを行列にすると次のようになります.

(anbn)=(2312)n1(a1b1) \begin{align} \begin{pmatrix} a_n \\ b_n \end{pmatrix} &= \begin{pmatrix} 2 & 3\\ 1 & 2 \end{pmatrix} ^{n-1} \begin{pmatrix} a_1 \\ b_1 \end{pmatrix} \end{align}

確率

次の問題を考えます.

エアコンのスイッチの状態はOFFOFFである.遠隔操作を1回行うと確率ppでエアコンのONONOFFOFFが入れ替わる.nn回遠隔操作をしたときエアコンがONONである確率を求めよ.(N1018N\leq 10^{18}) 出典 CODE FESTIVAL 2014 Middle C - eject

次のように変数を設定します. ai=ia_i = i回目の遠隔操作をしたときにエアコンがONONである確率 bi=ib_i = i回目の遠隔操作をしたときにエアコンがOFFOFFである確率 漸化式は次のように立ちます.

ai=pbi1+(1p)ai1bi=pai1+(1p)bi1 a_i = p b_{i-1} + (1-p)a_{i-1} \\ b_i = p a_{i-1} + (1-p)b_{i-1} \\

行列にします.ただし,a0=0,b0=1a_0=0,b_0=1です.

(anbn)=(1ppp1p)n(a0b0) \begin{align} \begin{pmatrix} a_n \\ b_n \end{pmatrix} &= \begin{pmatrix} 1-p & p\\ p & 1-p \end{pmatrix} ^{n} \begin{pmatrix} a_0 \\ b_0 \end{pmatrix} \end{align}

今までのものは全て,小さな問題の答えから大きな問題の答えを導くdp(dynamic programming:動的計画法)に分類されます.dpの漸化式が立ったときに,それが線形であり,同じ遷移をする場合に行列累乗が有効なことが多いです.

グラフのパス数

EDPC R - Walk

NN頂点の単調有効グラフGGで,長さ11の有向辺が長さKKのパスは何通りありますか.ただし同じ頂点を複数回通っても良い

NN次の正方行列で,頂点iiから頂点jjまでの有向辺があればAij=1A_{ij}=1,なければAij=0A_{ij}=0となるような隣接行列を考えます.

例えば,次の44頂点のグラフを隣接行列にすると次のようになります.

A=(0101001001000001) A = \begin{align} \begin{pmatrix} 0 &1 &0 &1 \\ 0 &0 &1 &0 \\ 0 &1 &0 &0 \\ 0 &0 &0 &1 \end{pmatrix} \end{align}

このとき,頂点iiから頂点jjへのパス数は次のように計算できます.

$$ (頂点iから頂点jへのパス数) = \sum {k=1}^4 A{ik} A_{kj} $$

これは,行列の積の定義とよく似ていて,A2A^2(i,j)(i,j)成分は,頂点iiから頂点jjへの長さ22のパス数を表します.よって,AnA^ni,ji,j成分から頂点iiからjjまでの長さnnのパス数を求めることができます.

なお,無向グラフの場合は双方向に有向辺が張っていると考え,Aij=AjiA_{ij}=A_{ji}とすることで同様に処理できます.

行列の級数

正方行列AAがある.A+A2+A3+A4+A5++ANA+A^2+A^3+A^4+A^5+\cdots+A^Nを求めよ.

次のようにXnX_nを定義します.

Xn=A1+A2+A3++An X_n = A^1 + A^2 + A^3 + \cdots + A^n

漸化式は次のように作れます.

X1=AXn=A+AXn1(n2) \begin{align} X_1 &= A\\ X_n &= A+AX_{n-1} \quad (n\geq 2) \end{align}

よって,

(XnI)=(AAOI)n1(AI) \begin{align} \begin{pmatrix} X_n \\ \hline I \end{pmatrix} &= \begin{pmatrix} \begin{array}{c|c} A & A\\ \hline O & I \end{array} \end{pmatrix} ^{n-1} \begin{pmatrix} A \\ \hline I \end{pmatrix} \end{align}

です.

半環

普通,行列の掛け算は次のように定義されています.

A=(a11a12a21a22)(b11b12b21b22)=(a11b11+a12b21a11b12+a12b22a21b11+a22b21a21b12+a22b22) A = \begin{align} \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix} \begin{pmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \end{pmatrix} = \begin{pmatrix} a_{11}\cdot b_{11}+a_{12}\cdot b_{21} & a_{11}\cdot b_{12}+a_{12}\cdot b_{22} \\ a_{21}\cdot b_{11}+a_{22}\cdot b_{21} & a_{21}\cdot b_{12}+a_{22}\cdot b_{22} \end{pmatrix} \end{align}

それぞれ要素の積を計算し,和を計算しています.ここで,「和」と「積」を別のものに置き換えることを考えます.例えば次のようにmax\max++に変えるとどうなるでしょうか.ここで,max(a1,a2,a3,)\max(a_1,a_2,a_3,\cdots)は,a1,a2,a3,a_1,a_2,a_3,\cdotsのうちの最大値を表します.

A=(a11a12a21a22)(b11b12b21b22)=(max(a11+b11,a12+b21)max(a11+b12,a12+b22)max(a21+b11,a22+b21)max(a21+b12,a22+b22)) A = \begin{align} \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix} \begin{pmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \end{pmatrix} = \begin{pmatrix} \max(a_{11}+b_{11},a_{12}+b_{21}) & \max(a_{11}+b_{12},a_{12}+b_{22}) \\ \max(a_{21}+b_{11},a_{22}+b_{21}) & \max(a_{21}+b_{12},a_{22}+b_{22}) \end{pmatrix} \end{align}

このmax,+\max,+で計算される行列ですが,実はこの行列においても高速な行列累乗の計算が可能です.こんな変な演算の世界で行列累乗をしてどうするんだと思いますが,例は後述します.もちろん,演算子を好き勝手変えていいわけではありません.いくつか条件があります.次に示す条件を満たす,集合と加法++と乗法 \cdot22つの二項演算,である必要があります.この性質を満たす集合と++\cdotの組を半環と言います.また,集合の要素を元と言います.

  • 加法において,結合法則が成り立ち,可換であり,単位元00を持つ.
    • (a+b)+c=a+(b+c)(a + b) + c = a + (b + c)
    • a+b=b+aa+b = b+a
    • 0+a=a+0=00 + a = a + 0 = 0
  • 乗法において,結合法則が成り立ち,単位元11を持つ.
    • (ab)c=a(bc)(a \cdot b) \cdot c = a \cdot (b \cdot c)
    • 1a=a1=a1 \cdot a = a \cdot 1 = a
  • 分配法則が成り立つ.
    • a(b+c)=(ab)+(ac)a \cdot (b+c) = (a\cdot b) + (a\cdot c)
    • (a+b)c=(ac)+(bc)(a+b)\cdot c = (a\cdot c) + (b\cdot c)
  • 乗法で,00(加法の単位元)と任意の元の積は00になる.
    • 0a=a0=00\cdot a = a\cdot 0 = 0

例えば,有理数の集合をR\mathbb{R}とすると,(R,+,)(\mathbb{R},+,\cdot)は半環をなす,という言い方をします.

では,先程のmax\max++の例は本当に半環をなしているかを確認してみましょう.この場合の集合もR\mathbb{R}(有理数全体)としておきます.先述した半環の定義だと,加法がmax\maxで,乗法が++に対応しています. まずは加法max\maxについて見ていきます.

  • max(max(a,b),c)=max(a,max(b,c))\max(\max(a,b),c) = \max(a,\max(b,c))
  • max(a,b)=max(b,a)\max(a,b) = \max(b,a)
  • max(,a)=max(a,)=\max(\infty,a) = \max(a,\infty) = \infty

max\maxは単位元を\inftyにすることで成立します.次に乗法++です.

  • (a+b)+c=a+(b+c)(a + b) + c = a + ( b+c)
  • 0+a=a+0=a0 + a = a + 0 = a

++の単位元は00です. 次に分配法則の確認です.ややこしいですが,次の式が成り立つことがわかります.

  • a+max(b,c)=max(a+b,a+c)a+\max(b,c) = \max(a+b,a+c)
  • max(a,b)+c=max(a+c,b+c)\max(a,b)+c = \max(a+c,b+c)

最後に加法max\maxの単位元\inftyを乗算++すると\inftyになることを確認します.

  • +a=a+=\infty +a = a + \infty = \infty

以上,厳密性には欠けますが(R,max,+)(\mathbb{R},\max,+)が半環をなしていることがわかりました.さて,次の節からは,いつもと違う半環の世界での行列累乗の例を見ていきます.

ANDとXOR

ABC009 D - 漸化式

定数C1,C2,C3,,CKC_1,C_2,C_3,\cdots,C_Kがあり,KK項間の漸化式が次のように定まる Ai(1iK)A_i \quad (1\leq i\leq K)は与えられる.

AK+1=(C1ANDAK)XOR(C2ANDAK1)XORXOR(CKANDA1) A_{K+1} = (C_1 \mathrm{AND} A_{K}) \mathrm{XOR} (C_2 \mathrm{AND} A_{K-1}) \mathrm{XOR} \cdots \mathrm{XOR} (C_K \mathrm{AND} A_{1})

このとき,ANA_Nを求めよ(1M1091\leq M\leq 10^{9}). なお,AND\mathrm{AND}はビットごとの論理積,XOR\mathrm{XOR}はビットごとの排他的論理和を表す.

この問題は(N,AND,XOR)(\mathbb{N},\mathrm{AND},\mathrm{XOR})が半環をなすことを利用して,ただの線形漸化式と見ることができます.なお,AND\mathrm{AND}XOR\mathrm{XOR}はビットごとで独立した演算であるため,各bitでmod  2\mod 2の掛け算とたし算をしていると見ることでも解くことができます.

ワーシャルフロイド法

ワーシャルフロイド法は,(R,min,+)(\mathbb{R},\min,+)の世界での行列累乗だと捉えることができます.

MojaCoderで類題を見つけました. Dungeon Attack (Hard)

関連問題

行列累乗がストレートに出ることは珍しく,考察の末に最後の一捻りとして出てくることが多い印象があります.全体的に難しいです.


  1. APG4b 計算量 https://atcoder.jp/contests/APG4b/tasks/APG4b_w ↩︎

  2. 実はこの計算量解析はあまり意味のあるものではありません.なぜなら,フィボナッチ数列は後の項に行けば行くほど桁数が増えるからです.後の項に行くほど,かけ算やたし算の計算コストは上がっていきます.ですので,O(logN)O(\log N)といってもN=107N=10^7の時点で結構時間がかかってしまいます.競プロでは109+710^9+7では割ったあまりを求めなさい,のように桁数を気にせずに計算できる場合が多いため,今回は考えないことにしています(競プロに限った話ではなく,大きな数を求めるときに異なる素数で割ったあまりを求めておいて,中国剰余原理で復元する,等の手法が使われる). ↩︎

Licensed under CC BY-NC-SA 4.0
Built with Hugo
テーマ StackJimmy によって設計されています。