ecsmtlir https://blog.hatena.ne.jp/ecsmtlir/ 競技プログラミング日記 https://ecsmtlir.hatenablog.com/ アルゴリズムと数学057 - Domino Tiling 解法: 行列冪乗 これも遷移が線形になるので，行列冪で解ける． 状態を \(2^{K}\) で持っておき， 次数\(2^{K}\)の行列を考える． まず\(N\)が小さい場合で考えてみる． DP による全探索をすると， 左から \(i\) 列目を決めるときは， \(i-1\) 列目の配置によってのみ影響を受ける． 実際，\(i-1\) 列目を敷き詰めるとき， \(i\) 列目においてどの場所にはみ出したかで， \(i\) 列目の敷き詰め方が決まる． (\(k \in K\) 列目においてはみ出しているか) \(\in 2\) と考えれば… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fecsmtlir.hatenablog.com%2Fentry%2F2023%2F12%2F13%2F063435" title=" アルゴリズムと数学057 - Domino Tiling - 競技プログラミング日記" 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 2023-12-13 06:34:35 rich https://ecsmtlir.hatenablog.com/entry/2023/12/13/063435 1.0 100%