JunKobayashi https://blog.hatena.ne.jp/JunKobayashi/ JunKobayashi's Diary https://junkobayashi.hatenablog.com/ ABCのE問題 ABC本番で敗北した問題 行列累乗 レピュニット数 競技プログラミングの問題で「行列の冪乗を求める」ことに帰着させられることが分かった時には俗に「行列累乗」と呼ばれている手法を利用するのが想定解となっていることが多い。これを実行するための処理内容は 「998244353 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 #競技プログラミング - Qiita 上記の記事で紹介されている「二分累乗法」とほとんど同じものとして記述することができ、扱う正方行列を\(N \times N\)型、冪乗の指数を\(x\)とすれば時間計算量\(O(N^3 \log x)\)で実行可能となる。なお、この処理は行列の積には結合法則が成り立っているこ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fjunkobayashi.hatenablog.com%2Fentry%2F2026%2F03%2F13%2F041840" title="行列累乗(1)（ABC448 E - Simple Division） - JunKobayashi&#39;s Diary" 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 2026-03-13 04:18:40 rich https://junkobayashi.hatenablog.com/entry/2026/03/13/041840 1.0 100%