pekempey https://blog.hatena.ne.jp/pekempey/ pekempey's blog https://pekempey.hatenablog.com/ https://yukicoder.me/problems/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… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpekempey.hatenablog.com%2Fentry%2F2019%2F12%2F15%2F045622" title="yukicoder No.950 行列累乗 - pekempey&#39;s blog" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2019-12-15 04:56:22 rich https://pekempey.hatenablog.com/entry/2019/12/15/045622 1.0 100%