yukicoder No.950 行列累乗

だいぶ手間取った。対角化は頭にちらついてはいたけど経験上、行列の成分が任意のときにこれをやると沼にはまるので避けた。結果として避けてよかったのかな。たぶんどっちを選ぶかは好みの問題な気がする。

行列でなく整数で $a^n=b \pmod{p}$ を求める問題であれば BSGS (baby step giant step) と呼ばれるアルゴリズムで解けます。今回の問題も

\begin{equation}
\begin{pmatrix}
a & 0 \\
0 & a
\end{pmatrix}^n
=
\begin{pmatrix}
b & 0 \\
0 & b
\end{pmatrix}
\end{equation}

という入力を考えれば整数のときの問題になりますから、整数のときより難しい問題だとわかります。そうなると BSGS が解法だろうと予想ができます。

一応 BSGS についても簡単に説明しておきます。BSGS というのは $a^n \equiv b \pmod{p}$ となる最小の負でない整数 $n$ を求めるアルゴリズムです。ここでは $a$, $b$ が整数のときを考えますが、行列でも同じようにできます。

BSGS はまず $a^0, a^1, a^2, a^3, \ldots, a^{9999}$ のなかに $b$ があるか調べ、なければ $a^{10000},a^{10001}, \ldots, a^{19999}$ のなかに $b$ があるか調べ、さらになければ $a^{20000},a^{20001},\ldots,a^{29999}$ を調べ、ということを繰り返すアルゴリズムです。この 10000 の部分はなんでもいいんですが、ここでは 10000 としておきます。このアルゴリズムを速く動かすことを考えましょう。$k$ 回目の反復では $a^{10000k},a^{10000k+1},\ldots, a^{10000k+9999}$ のなかに $b$ があるかを調べることになります。これは $a^0,a^1,a^2,\ldots,a^{9999}$ のなかに $b a^{-10000k}$ があるのか調べるのと同じことです。よって $\{a^0,a^1,a^2,\ldots,a^{9999}\}$ を集合のためのデータ構造を使って表しておいて、$b, b a^{-10000}, b a^{-20000}, \ldots$ がこのなかにあるか調べていけばよいということになります。

$A$ に逆行列がない場合は後回しにして $A$ の逆行列がある場合を考えます。つまり $\det A \ne 0$ です。このとき累乗 $E,A,A^2,A^3,\ldots$ をならべていくと、どこかでまた $E$ に戻ります。練習だとおもってこれも証明してみます。

まず二次正方行列は $p^4$ 通りしかありません。そのため $p^4+1$ 個の行列 $E, A, A^2, \ldots, A^{p^4}$ をもってくると鳩の巣原理よりかならず同じものがあります。それを $A^x$, $A^y$ とします。すると $A^x A^{y-x} = A^y = A^x$ になりますが、$A$ は逆行列をもつので左から $A^{-x}$ を掛けると $A^{y-x}=E$ となります。これで証明が終わりました。

はじめて $E$ に戻るときの指数を $ m $ としましょう。そうするとこたえは $1$ 以上 $ m $ 以下のどこかにあります。もし $ m $ がそんなに大きくなければ BSGS によって解くことができます。ちなみに BSGS は $O(\sqrt{m})$ で動きます。

さてそうなると $ m $ がどのくらいまで大きくなるかが気になります。さきほどの証明からわかるように $p^4$ よりは小さいです。もう少ししぼります。

ケーリーハミルトンの定理というのがあって、どんな二次正方行列も $A^2 - (a+d) A + (ad-bc) E = O$ を満たします。この定理を使うと $A^n=\square A + \square E$ と表せることがわかります。なぜかというと $A^n$ を $A^2 - (a+d) A + (ad-bc)E$ で割ると $A^n=\bigcirc (A^2 - (a+d) A + (ad-bc)E) + \square A + \square E$ となるからです。ただしここでいう割り算は行列の割り算ではなく多項式の割り算です。$\square$ には $p$ 通りの整数しか入りませんから、$A^n$ は $p^2$ 通りしかありえないことがわかります。

この見積もりが正しいのか、実際に $p=11$ や $p=13$ で確かめてみるといいでしょう。このくらいの周期をもつ行列がすぐに見つかります。そのため素朴に BSGS をするだけでは解けないこともわかります。

こういうときは何かしらの必要条件を考えて、探索範囲を狭めましょう。今回であれば行列式が使えそうです。$\det A^n = (\det A)^n = \det B$ は成り立たないといけないので、ここから $n$ がどのような数なのかがわかります。これを満たすような最小の正の整数 $n$ は BSGS で見つけられます。そうすると $(\det A)^k=1$ になる最小の正の整数 $k$ をつかって、答えは $n, n+k, n+2k, \ldots$ のいずれかであることがわかります。

よって $A^{n+ sk} = B$ を満たす負でない整数 $s$ を見つける問題を解けばいいということになります。いま $A$ は逆行列をもつので $(A^k)^s=B A^{-n}$ としてよいです。これはもとの問題とほとんど同じ形をしていて、唯一違うのは $\det A^k = 1$ であることです。

$\det A=1$ であれば $\det A^2 = 1$ ですし、一般に $\det A^k=1$ です。そのため $E,A,A^2,A^3,\ldots$ はどれも行列式が 1 です。直感的には行列式のあたいが何でもよかったときと比べると周期が短くなりそうです。その直感を信じてプログラムで実験してみました。するとたしかに短くて $2p$ くらいで抑えられていることが分かりました。よって BSGS で解けます。

あとづけですが、周期が $2p$ で抑えられることを証明しましょう。$A^n=\square A + \square E$ と表せることはさきほどの通りです。ここから先では $A$ と $E$ を多項式のように扱います。つまり $aA + bE = cA + dE$ と $a=c$ かつ $b=d$ を同値として扱います。$X=\square A + \square E$ を固定します。このとき $X,2X,3X,\ldots,(p-1)X$ の行列式は $\det X, 2^2 \det X, 3^2 \det X, \ldots, (p-1)^2 \det X$ になります。つまりこの $p-1$ 個のなかで $X$ と同じ行列式をもつのは唯一 $(p-1)X$ だけです。

$\{X, 2X, 3X, \ldots, (p-1) X\}$ を $X$ の軌道と呼ぶことにします。軌道の大きさはかならず $p-1$ です。さきほどの議論から、$\det X=1$ のとき $X$ の軌道のなかに行列式が 1 になるものはちょうど 2 個あります。$A^n$ はいくつかの軌道に分解できます。軌道の大きさが $p-1$ なので、軌道の種類はたかだか $p^2 / (p-1)$ 通りしかありません。各軌道に行列式が 1 の行列が 2 つあるのなら、行列式が 1 の行列はたかだか $2p^2 / (p-1)$ 個であることがわかります。

$2p$ で抑えられることを示すつもりが、すこし違う結果になりましたが、計算量を考える上では問題ないでしょう。たぶん $\square A + \square E$ の形のものが $p^2$ 通りというのがもう少し抑えられます。ゼロ以外の多項式を考えているので $p^2-1$ 通り、これだと $2(p+1)$ で抑えられます。

$\det A = 0$ の場合ですが、自分はケーリーハミルトンの定理 $A^2=(a+d)A$ をつかって $A^n=(a+d)^{n-1} A$ として解きました。割りとこっちも思いつくのに時間がかかってます。こうすればただの整数のときの問題と同じです。

ケーリーハミルトンの定理、対角化と違って場合分けがでてこないから心が落ち着く。高校時代 $A^n$ を求めるときもケーリーハミルトンの定理でばかり求めていた気がする（遠い記憶。このみとか関係なしに対角化に誘導されるのが現実だけど）。