Day 175-Q2 — 2026-10-11 | 次数 2 以下の全域部分グラフを「閉路の数 × 路の数」で数える（2 変数の係数を 1 つの整数に詰めたプラグ DP）

📋 コピーimport sys

MOD = 998244353
S = 80                                          # 1 つの係数に使うビット数


def partner(st, pos, ty):
    # 位置 pos の括弧 ty（1='(' / 2=')'）の相方の位置。3 は括弧として数えない
    d = 0
    step = 1 if ty == 1 else -1
    p = pos
    while True:
        t = (st >> (2 * p)) & 3
        if t == ty:
            d += 1
        elif t == 3 - ty:
            d -= 1
            if d == 0:
                return p
        p += step


def main():
    data = sys.stdin.read().split()
    h, w, k, c = int(data[0]), int(data[1]), int(data[2]), int(data[3])
    g = data[4:4 + h]
    if w > h:                                   # プロファイルの長さを短い辺にする
        g = [''.join(g[i][j] for i in range(h)) for j in range(w)]
        h, w = w, h
    E = 2 * k + 1                               # 端点の数 e = 0..2k
    slots = E * (c + 1)                         # 区画番号 = 閉路の数 * E + 端点の数
    mask = (1 << (S * slots)) - 1
    CYC = S * E                                 # 閉路が 1 つ増える = この幅だけ左シフト
    # 端点が d 増えたとき e > 2k になった区画は、次の閉路の数の区画へはみ出すので消す
    keep1 = sum(((1 << S) - 1) << (S * (cc * E + e)) for cc in range(c + 1) for e in range(1, E))
    keep2 = sum(((1 << S) - 1) << (S * (cc * E + e)) for cc in range(c + 1) for e in range(2, E))
    free = [[ch == '.' for ch in row] + [False] for row in g] + [[False] * (w + 1)]

    B = S // 8                                  # 1 区画のバイト数
    nb = B * slots
    frm = int.from_bytes

    def reduce(v):
        # 区画ごとに mod。シフトで 1 区画ずつ取り出すと区画数の 2 乗かかるので、バイト列で切り出す
        bs = v.to_bytes(nb, 'little')
        return frm(b''.join((frm(bs[t:t + B], 'little') % MOD).to_bytes(B, 'little')
                            for t in range(0, nb, B)), 'little')

    # 状態数 < 2^12（幅 7 以下）、mod 直後の区画 < 2^30、1 マスで総和は高々 4 倍 → 30+12+2*マス数 < 80
    per = max(1, (S - 1 - 30 - 12) // (2 * w))
    cur = {0: 1}
    for i in range(h):
        if i % per == 0:                        # per 行ごとにだけ mod を取る（Step 5 の上限）
            cur = {st << 2: reduce(v) for st, v in cur.items() if st >> (2 * w) == 0}
        else:
            cur = {st << 2: v for st, v in cur.items() if st >> (2 * w) == 0}
        for j in range(w):
            nxt = {}
            get = nxt.get
            fr = free[i][j]
            down_ok = free[i + 1][j]
            right_ok = free[i][j + 1]
            sj = 2 * j
            sj1 = sj + 2
            clr = ~((3 << sj) | (3 << sj1))
            for st, val in cur.items():
                a = (st >> sj) & 3
                b = (st >> sj1) & 3
                base = st & clr
                if not fr:
                    if a == 0 and b == 0:
                        nxt[st] = get(st, 0) + val
                    continue
                if a == 0 and b == 0:
                    v1 = (val << S) & keep1
                    if down_ok and right_ok:
                        s2 = base | (1 << sj) | (2 << sj1)
                        nxt[s2] = get(s2, 0) + val
                    if down_ok:
                        s2 = base | (3 << sj)
                        nxt[s2] = get(s2, 0) + v1
                    if right_ok:
                        s2 = base | (3 << sj1)
                        nxt[s2] = get(s2, 0) + v1
                    nxt[base] = get(base, 0) + ((val << (2 * S)) & keep2)
                elif a == 0 or b == 0:
                    x = a | b
                    if down_ok:
                        s2 = base | (x << sj)
                        nxt[s2] = get(s2, 0) + val
                    if right_ok:
                        s2 = base | (x << sj1)
                        nxt[s2] = get(s2, 0) + val
                    if x == 3:
                        s2 = base
                    else:
                        q = partner(st, j if a else j + 1, x)
                        s2 = base | (3 << (2 * q))
                    nxt[s2] = get(s2, 0) + ((val << S) & keep1)
                else:
                    if a == 1 and b == 2:       # 同じ線の両端: 閉路が 1 つ閉じる
                        nxt[base] = get(base, 0) + ((val << CYC) & mask)
                        continue
                    if a == 3 and b == 3:
                        s2 = base
                    elif a == 3 or b == 3:
                        y, pos = (b, j + 1) if a == 3 else (a, j)
                        q = partner(st, pos, y)
                        s2 = (base & ~(3 << (2 * q))) | (3 << (2 * q))
                    elif a == 2 and b == 1:
                        s2 = base
                    elif a == 1 and b == 1:
                        q = partner(st, j + 1, 1)
                        s2 = (base & ~(3 << (2 * q))) | (1 << (2 * q))
                    else:
                        q = partner(st, j, 2)
                        s2 = (base & ~(3 << (2 * q))) | (2 << (2 * q))
                    nxt[s2] = get(s2, 0) + val
            cur = nxt
    v = reduce(cur.get(0, 0))
    m1 = (1 << S) - 1
    out = []
    for cc in range(c + 1):
        out.append(' '.join(str((v >> (S * (cc * E + 2 * m))) & m1) for m in range(k + 1)))
    print('\n'.join(out))


main()