POJ No. 3233 Matrix Power Series
※このエントリは競プロで圧倒的成長 Advent Calendar 2015の7日目のエントリです．
昨日の奴，書いてアドベントカレンダーにリンク貼ってなかった．
問題要約
[latex]S=A+A2+A3+A4......Ak[/latex]の各要素の値を[latex]M[/latex]で割った値を出力する．
解法
蟻本の例題．ほぼ蟻本と同じ方法だけど少しだけ違う方法で解いた． [latex] \begin{pmatrix} Ak \ S
\end{pmatrix}
\begin{pmatrix}
A & I \
A & I
\end{pmatrix}^k
\begin{pmatrix}
I \
0
\end{pmatrix}
[/latex]
という式が成り立つので，昨日の記事のように行列の冪乗を計算すれば求めることができる．
