Day 171-Q3 — 2026-10-06 | 盤面のハミルトン閉路の数（括弧列で連結を持つプラグ DP。2 本の線が出会ったときに相手の括弧を付け替える）

📋 コピーimport sys

MOD = 998244353


def main():
    data = sys.stdin.read().split()
    h, w = int(data[0]), int(data[1])
    g = data[2:2 + h]
    if w > h:                                   # 狭い方を幅にする（状態数は幅で決まる）
        g = [''.join(g[i][j] for i in range(h)) for j in range(w)]
        h, w = w, h
    cells = [(i, j) for i in range(h) for j in range(w) if g[i][j] == '.']
    if not cells:
        print(0)
        return
    last = cells[-1]
    # 状態: 幅 w+1 個の差し口。0=なし 1=左括弧 2=右括弧。2 ビットずつ整数に詰める
    # 位置 j は「セル (i,j) の上から入る線」、位置 w は処理中セルの左から入る線
    cur = {0: 1}
    ans = 0
    for i in range(h):
        # 行の頭: 左からの線は無いはず（位置 w が 0 のものだけ残す）
        cur = {s: c for s, c in cur.items() if (s >> (2 * w)) & 3 == 0}
        for j in range(w):
            nxt = {}
            sh_u = 2 * j
            sh_l = 2 * w
            free = g[i][j] == '.'
            down_ok = i + 1 < h and g[i + 1][j] == '.'
            right_ok = j + 1 < w and g[i][j + 1] == '.'
            is_last = (i, j) == last
            for s, c in cur.items():
                up = (s >> sh_u) & 3
                lf = (s >> sh_l) & 3
                base = s & ~((3 << sh_u) | (3 << sh_l))
                if not free:
                    if up == 0 and lf == 0:
                        nxt[base] = nxt.get(base, 0) + c
                    continue
                if up == 0 and lf == 0:
                    # 新しい角: 下と右へ出す（左括弧が下、右括弧が右）
                    if down_ok and right_ok:
                        t = base | (1 << sh_u) | (2 << sh_l)
                        nxt[t] = nxt.get(t, 0) + c
                elif up == 0 or lf == 0:
                    v = up | lf
                    if down_ok:
                        t = base | (v << sh_u)
                        nxt[t] = nxt.get(t, 0) + c
                    if right_ok:
                        t = base | (v << sh_l)
                        nxt[t] = nxt.get(t, 0) + c
                else:
                    # 2 本が合流する
                    if lf == 1 and up == 2:
                        # 閉路が閉じる: 最後のセルで他に差し口が無いときだけ
                        if is_last and base == 0:
                            ans += c
                        continue
                    if lf == 1 and up == 1:
                        # 2 つの左括弧: 上の線の相手（右括弧）を左括弧に変える
                        t = base
                        depth = 0
                        for k in range(j + 1, w):
                            x = (t >> (2 * k)) & 3
                            if x == 1:
                                depth += 1
                            elif x == 2:
                                if depth == 0:
                                    t ^= (3 << (2 * k))   # 2 -> 1
                                    break
                                depth -= 1
                    elif lf == 2 and up == 2:
                        # 2 つの右括弧: 左の線の相手（左括弧）を右括弧に変える
                        t = base
                        depth = 0
                        for k in range(j - 1, -1, -1):
                            x = (t >> (2 * k)) & 3
                            if x == 2:
                                depth += 1
                            elif x == 1:
                                if depth == 0:
                                    t ^= (3 << (2 * k))   # 1 -> 2
                                    break
                                depth -= 1
                    else:
                        # lf == 2, up == 1: 2 つの弧をつなぐだけ
                        t = base
                    nxt[t] = nxt.get(t, 0) + c
            cur = {k: v % MOD for k, v in nxt.items()}
    print(ans % MOD)


main()