この記事はZennに投稿したものと同じです.
これはなに
行列累乗と呼ばれる競プロのテクニックの概要と,それを用いる例をひたすら挙げていきます.競プロチックな話題ではありますが,行列が役立つ場面の例の紹介として,非競プロerでも楽しめると思います.ただし,数列と行列に関する用語がある程度わかっている人向けです.
なお,この記事は長野高専 Advent Calender 2022の2日目の記事です。
原理(フィボナッチ数列の例)
次の式で表される数列を考えます.
F1F2Fn=1=1=Fn−1+Fn−2 (n≥3)
これはフィボナッチ数列という名で知られている,F=(1,1,2,3,5,8,13,21,34,⋯)という前の2項の和が次の項になる数列です.これの第n項目をプログラミングで求めることにします.第1項目から第n項目までを求めるのではなく,第n項目のみ求めれば良いことに注意です.それっぽいコードを次に示します.
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
文をn回くらい回すので計算量はO(n)です(計算量についてこちらを参照してください).
では,n=1015項目を求めたい場合はどうでしょうか.このコードでは,実行が終わりません.
行列で表現する
ここで,行列です.フィボナッチ数列の定義より,次の式は成り立ちます.
(FnFn−1)=(1110)(Fn−1Fn−2)
具体的に計算してみます.
(21)=(1110)(11)
(32)=(1110)(21)
(53)=(1110)(32)
前の2項から次の項が生成されていることがわかりますね.
これらの結果を使って次のような変形を考えます.
(53)=(1110)(32)=(1110)(1110)(21)=(1110)(1110)(1110)(11)=(1110)3(11)
始めの2項に同じ行列を3回掛け算することで3つ後の項が出てきました.これを繰り返すと次が成り立つことがわかります.
(FnFn−1)=(1110)n−2(F2F1)
第10項目を求めたいときは次のように計算できます.
(F10F9)=(1110)8(F2F1)=(89555534)(11)=(14489)
フィボナッチ数列は1,1,2,3,5,8,13,21,34,55,89,144,⋯であるため,確かにあっています.
便利そうな式が行列によって完成しました.漸化式の悪いところは前の項の値がわかっていないと次の項が計算できないことですが,この式は特定の項をダイレクトに表すことに成功しています.行列のn乗が高速に計算できればフィボナッチ数列の第n項が高速に計算できそうです.
累乗の高速計算
行列Aのn乗であるAnを計算するのに,ナイーブな方法だとn−1回の行列同士の掛け算が発生します.この行列同士の掛け算の回数が少なくなることを高速化と呼ぶことにします.
A128を考えてみましょう.
- AにAをかけてA2
- A2にAをかけてA3
⋯
- A127にAをかけてA128
全部で127回の掛け算が必要ですね.では,128という特徴的な数に注目して次のように計算したらどうでしょうか.
- AにAをかけてA2
- A2にA2をかけてA4
- A4にA4をかけてA8
- A8にA8をかけてA16
- A16にA16をかけてA32
- A32にA32をかけてA64
- A64にA64をかけてA128
全部で,7回の掛け算でA128が計算できました.127回から7回という驚異の回数削減です.
実は,これは128のような2の冪数に限った話ではありません.先程,A1,A2,A4,A8,A16,⋯を求めましたが,これらを掛け合わせることで任意のAnが計算できます(指数法則AaAb=Aa+bが成り立つことに注意).
- A12=A8A4
- A39=A32A4A2A1
- A127=A64A32A16A8A4A2A1
これらは,Aの(2進数表記したとき,1である位)乗を掛け算したものになっています.
上の例では,12(10)=1100(2)であり,1である位は4の位と8の位なので12=8+4と12を2の冪数の和で表すことができます.
このような手法をダブリングや繰り返し二乗法と呼びます.
それっぽいコードを次に示します.計算量はO(logN)です.O(N)に比べて非常に高速です.
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]}です")
|
線形漸化式
フィボナッチ数列は2項間の漸化式でしたが,k項間の線形漸化式でも可能です.
3項の場合
次で定義される数列aのn項目を求めよ.
a1an=a2=a3=1=2an−1−4an−2+3an−3 (n≥4)
この漸化式は次のような行列で表されます.
⎝⎛anan−1an−2⎠⎞=⎝⎛210−401300⎠⎞n−3⎝⎛a3a2a1⎠⎞
実際に行列を計算すると確かに成立していることがわかります.
一般に,k+1項間の漸化式はk×kの行列を使って表され,k×kの行列同士の掛け算はk3回の掛け算が必要であるため,第n項を求めるのにO(k3logn)かかります.
なお,k+1項間の線形漸化式の第n項はkitamasa法と呼ばれる手法で(k2logn)で求めることが可能です.こちらもダブリングを使った手法です.
定数項がある場合
a,b,m,x0を使って線形合同法で乱数を生成する.このときのn番目の乱数xnを求めよ
ただし,線形合同法とは,
xi+1=axi+b(modm)
の漸化式で疑似乱数を生成する手法である.
定数項がある場合は1の行を付け足して次のように作ることができます.
(xn1)=(a0b1)n(x01)
複数変数の線形漸化式
複数の変数で表される漸化式にも応用できます
平方根を含む数の累乗
次の問題を考えます.
(2+3)nはいくつか?a+b3の形式になるのでa,bを求めよ.
nが大きいと展開が厄介になりそうなことが想像できますね.
とりあえず,2+3の累乗を次のように文字で置きます.
Xn=(an+bn3)
XnからXn+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}
a_1&=b_1=1 \\
a_{n+1} &= 2a_{n} + 3b_n \\
b_{n+1} &= a_n + 2b_n
\end{align}
$$
これを行列にすると次のようになります.
(anbn)=(2132)n−1(a1b1)
確率
次の問題を考えます.
エアコンのスイッチの状態はOFFである.遠隔操作を1回行うと確率pでエアコンのONとOFFが入れ替わる.n回遠隔操作をしたときエアコンがONである確率を求めよ.(N≤1018) 出典 CODE FESTIVAL 2014 Middle C - eject
次のように変数を設定します.
ai=i回目の遠隔操作をしたときにエアコンがONである確率
bi=i回目の遠隔操作をしたときにエアコンがOFFである確率
漸化式は次のように立ちます.
ai=pbi−1+(1−p)ai−1bi=pai−1+(1−p)bi−1
行列にします.ただし,a0=0,b0=1です.
(anbn)=(1−ppp1−p)n(a0b0)
今までのものは全て,小さな問題の答えから大きな問題の答えを導くdp(dynamic programming:動的計画法)に分類されます.dpの漸化式が立ったときに,それが線形であり,同じ遷移をする場合に行列累乗が有効なことが多いです.
グラフのパス数
EDPC R - Walk
N頂点の単調有効グラフGで,長さ1の有向辺が長さKのパスは何通りありますか.ただし同じ頂点を複数回通っても良い
N次の正方行列で,頂点iから頂点jまでの有向辺があればAij=1,なければAij=0となるような隣接行列を考えます.
例えば,次の4頂点のグラフを隣接行列にすると次のようになります.

A=⎝⎛0000101001001001⎠⎞
このとき,頂点iから頂点jへのパス数は次のように計算できます.
$$
(頂点iから頂点jへのパス数) = \sum {k=1}^4 A{ik} A_{kj}
$$
これは,行列の積の定義とよく似ていて,A2の(i,j)成分は,頂点iから頂点jへの長さ2のパス数を表します.よって,Anのi,j成分から頂点iからjまでの長さnのパス数を求めることができます.
なお,無向グラフの場合は双方向に有向辺が張っていると考え,Aij=Ajiとすることで同様に処理できます.
行列の級数
正方行列Aがある.A+A2+A3+A4+A5+⋯+ANを求めよ.
次のようにXnを定義します.
Xn=A1+A2+A3+⋯+An
漸化式は次のように作れます.
X1Xn=A=A+AXn−1(n≥2)
よって,
(XnI)=(AOAI)n−1(AI)
です.
半環
普通,行列の掛け算は次のように定義されています.
A=(a11a21a12a22)(b11b21b12b22)=(a11⋅b11+a12⋅b21a21⋅b11+a22⋅b21a11⋅b12+a12⋅b22a21⋅b12+a22⋅b22)
それぞれ要素の積を計算し,和を計算しています.ここで,「和」と「積」を別のものに置き換えることを考えます.例えば次のようにmaxと+に変えるとどうなるでしょうか.ここで,max(a1,a2,a3,⋯)は,a1,a2,a3,⋯のうちの最大値を表します.
A=(a11a21a12a22)(b11b21b12b22)=(max(a11+b11,a12+b21)max(a21+b11,a22+b21)max(a11+b12,a12+b22)max(a21+b12,a22+b22))
このmax,+で計算される行列ですが,実はこの行列においても高速な行列累乗の計算が可能です.こんな変な演算の世界で行列累乗をしてどうするんだと思いますが,例は後述します.もちろん,演算子を好き勝手変えていいわけではありません.いくつか条件があります.次に示す条件を満たす,集合と加法+と乗法 ⋅ の2つの二項演算,である必要があります.この性質を満たす集合と+と⋅の組を半環と言います.また,集合の要素を元と言います.
- 加法において,結合法則が成り立ち,可換であり,単位元0を持つ.
- (a+b)+c=a+(b+c)
- a+b=b+a
- 0+a=a+0=0
- 乗法において,結合法則が成り立ち,単位元1を持つ.
- (a⋅b)⋅c=a⋅(b⋅c)
- 1⋅a=a⋅1=a
- 分配法則が成り立つ.
- a⋅(b+c)=(a⋅b)+(a⋅c)
- (a+b)⋅c=(a⋅c)+(b⋅c)
- 乗法で,0(加法の単位元)と任意の元の積は0になる.
- 0⋅a=a⋅0=0
例えば,有理数の集合をRとすると,(R,+,⋅)は半環をなす,という言い方をします.
では,先程のmaxと+の例は本当に半環をなしているかを確認してみましょう.この場合の集合もR(有理数全体)としておきます.先述した半環の定義だと,加法がmaxで,乗法が+に対応しています.
まずは加法maxについて見ていきます.
- max(max(a,b),c)=max(a,max(b,c))
- max(a,b)=max(b,a)
- max(∞,a)=max(a,∞)=∞
maxは単位元を∞にすることで成立します.次に乗法+です.
- (a+b)+c=a+(b+c)
- 0+a=a+0=a
+の単位元は0です.
次に分配法則の確認です.ややこしいですが,次の式が成り立つことがわかります.
- a+max(b,c)=max(a+b,a+c)
- max(a,b)+c=max(a+c,b+c)
最後に加法maxの単位元∞を乗算+すると∞になることを確認します.
- ∞+a=a+∞=∞
以上,厳密性には欠けますが(R,max,+)が半環をなしていることがわかりました.さて,次の節からは,いつもと違う半環の世界での行列累乗の例を見ていきます.
ANDとXOR
ABC009 D - 漸化式
定数C1,C2,C3,⋯,CKがあり,K項間の漸化式が次のように定まる
Ai(1≤i≤K)は与えられる.
AK+1=(C1ANDAK)XOR(C2ANDAK−1)XOR⋯XOR(CKANDA1)
このとき,ANを求めよ(1≤M≤109).
なお,ANDはビットごとの論理積,XORはビットごとの排他的論理和を表す.
この問題は(N,AND,XOR)が半環をなすことを利用して,ただの線形漸化式と見ることができます.なお,ANDとXORはビットごとで独立した演算であるため,各bitでmod2の掛け算とたし算をしていると見ることでも解くことができます.
ワーシャルフロイド法
ワーシャルフロイド法は,(R,min,+)の世界での行列累乗だと捉えることができます.
MojaCoderで類題を見つけました.
Dungeon Attack (Hard)
関連問題
行列累乗がストレートに出ることは珍しく,考察の末に最後の一捻りとして出てくることが多い印象があります.全体的に難しいです.