mayokoex https://blog.hatena.ne.jp/mayokoex/ mayoko’s diary https://mayokoex.hatenablog.com/ AOJ 問題 Three-way Branch | Aizu Online JudgeW*H のグリッドが与えられる。これらのうち, N 個のセルは通れなくなっている。あるセル(x, y) からは (x-1, y+1) or (x, y+1) or (x+1, y+1) にのみ行ける場合, (0, 0) から (W-1, H-1) までの経路は何通りあるか。 解法 W がまぁまぁ小さくて H が超でかいので行列累乗な感じがします。障害物は N 個しかないので, 障害物のある行になるまでは行列累乗 障害物ある行では 対応するところの場合の数を 0 にする というようにやれば O(W^3 log H * … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2016%2F08%2F30%2F223151" title="AOJ 2397 Three-way Branch - mayoko’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 2016-08-30 22:31:51 rich https://mayokoex.hatenablog.com/entry/2016/08/30/223151 1.0 100%