Area1 https://blog.hatena.ne.jp/Area1/ Area1のif(memo[i][j]) https://area.hateblo.jp/ 分割統治 行列 POJ 問題 nxnの行列Aが与えられる。S=A+A^2+A^3+...+A^kを計算し、各要素をmで割ったあまりを求めよ。 やりかた 行列の累乗は繰り返し二乗でできるとしても単純にやったら確実にTLEする。なのでうまく分割統治しつつメモ化しておくことで通すことができる。数列を左右に二分割する。すると A + A^2 + A^3 + A^4 + A^5 + A^6 + A^7 + A^8 = A(E + A + A^2 + A^3) + A^4(E + A + A^2 + A^3) となり、(E + A + A^2 + A^3)という構造が左右に現れる。この構造はさらにE(E + A) + A^2(E… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Farea.hateblo.jp%2Fentry%2F2017%2F01%2F28%2F023755" title="POJ 3233 Matrix Power Series - Area1のif(memo[i][j])" 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 2017-01-28 02:37:55 rich https://area.hateblo.jp/entry/2017/01/28/023755 1.0 100%