行列累乗力が足りない…！

行列累乗がよくわからない。どうしたらその遷移行列を見つけられるのか？
とりあえず制約からヒントを得よう。
n<=150くらい。これが行列のサイズになる。n^3log kができるくらいのサイズ。
k<=10^20とかとにかく大きい値。powerの指数になる。
nはアルファベットの数など、見えにくい形のものも多い。
そもそも行列の掛け算とは、

C_ij = Σk (A_ik B_kj)

というシンプルな形。
新しい状態は、前の状態と遷移行列の掛け算と足し算でできるということ。
掛け算と足し算は、環とか半環なら行列もそれになって、バイナリ法が使えるらしい？から、色々な環・半環で考えることが出来る？。
で、どうやってその遷移行列を見つけるのか？わからない。誰か教えて。
とにかく制約から行列累乗を疑う程度のことはしてみよう。
また、行列は様々な特殊形があって、計算量を落とせることがある。そこらへんは、気づいたら適当にぐぐってみる程度はしてみよう。
ちなみに、行列の累乗の総和はhttp://d.hatena.ne.jp/simezi_tan/20120101/1325399315によると、

[ A O ]
[ I I ]

と並べた行列を累乗することによって計算できるらしい。