Day 167-Q2 — 2026-10-01 | 壁付き盤面のドミノ敷き詰めの数え上げ（マスごとのプロファイル DP と、狭い方を幅にする転置）

📋 コピーimport sys
MOD = 998244353
def count(g):
    H, W = len(g), len(g[0])
    if W > H:                                  # 狭い方を幅にする（状態数は高々 2^min(H,W)）
        g = ["".join(g[i][j] for i in range(H)) for j in range(W)]
        H, W = W, H
    dp = {0: 1}
    for i in range(H):
        for j in range(W):
            b = 1 << j
            new = {}
            def add(m, v):
                new[m] = (new.get(m, 0) + v) % MOD
            wall = g[i][j] == '#'
            down = i + 1 < H and g[i+1][j] == '.'
            right = j + 1 < W and g[i][j+1] == '.'
            for m, v in dp.items():
                if m & b:                      # このマスは上から縦置きで埋まっている
                    add(m ^ b, v)              # （壁には置かないので wall と同時には起きない）
                elif wall:
                    add(m, v)                  # 壁: 何も置かず次へ
                else:
                    if down: add(m | b, v)                         # 縦置き: 下のマスを埋める
                    if right and not (m & (b << 1)): add(m | (b << 1), v)   # 横置き: 右のマスを埋める
            dp = new
    return dp.get(0, 0)
def main():
    H, W = map(int, sys.stdin.readline().split())
    g = [sys.stdin.readline().strip() for _ in range(H)]
    print(count(g))
if __name__ == "__main__": main()