問題
$H\times W$ の盤面があり、各マスは .（空き）か #（壁）である。上下左右に隣り合う空きマスの間の辺から何本かを選び、どの空きマスもちょうど 1 本の路に属するようにする（各空きマスにつながる選んだ辺は 2 本以下、閉路なし）。このとき空きマスは何本かの互いに素な路に分かれる。辺を 1 本も持たない空きマスは、それだけで 1 本の路と数える。
$m=1,2,\dots,K$ のそれぞれについて、路がちょうど $m$ 本になる辺の選び方の数を $998244353$ で割った余りを出力せよ。選んだ辺の集合が異なれば異なる選び方とする。
入力形式
H W K
S_1
...
S_H制約
| # | 条件 |
|---|---|
| 1 | $1\le H,W\le30$、$\min(H,W)\le6$ |
| 2 | $1\le K\le20$ |
| 3 | $S_i$ は . と # からなる長さ $W$ の文字列 |
入出力例
入力例1
2 2 4
..
..出力例1
4 6 4 1（$m=2$ は「辺 2 本の 2 通り」と「3 マスの路＋1 マスの 4 通り」で 6）
入力例2
3 3 5
...
.#.
...出力例2
8 28 56 70 56（空きマスは長さ 8 の輪。輪から $m$ 本の辺を外すと $m$ 本の路になるので $\binom8m$）
入力例3
2 3 3
...
...出力例3
8 25 33（3 例とも辺集合の全探索と一致）
背景と出典
- プラグ DP（Day171-Q3・Day172-Q2・Day173-Q1）: 1 マスずつ処理し、処理済みと未処理の境界（プロファイル）を横切る線を「プラグ」として持つ。線の両端が境界に出ていれば括弧
()、片方が既に路の端点で終わっていれば記号 3 - 本問の数え上げは「各成分が路の全域部分グラフ（線形森）を、成分数ごとに数える」こと。成分数 = 空きマス数 − 辺数なので、辺数ごとに数えても同じ。本問は端点の数 $e$（路 1 本につき 2、1 マスの路も 2）で数える
- 状態に $e$ を足す素直な方法は、Day173-Q1 のようにキーを
st << 6 | eにする。$K=10$ だと同じプロファイルが最大 21 通りの $e$ に分かれ、括弧の相方探しも 21 回繰り返す。本問は同じプロファイルの $e=0..2K$ の値を 80 ビットずつ 1 つの整数に詰め、端点が 1 つ増える遷移を「80 ビット左シフト」に置き換える
本問は自作。$n\times n$ の $m=1$ の値は Day173-Q1 の端点自由ハミルトン路の数 1, 4, 20, 276, 4324, 229348, 13535280 と一致した（本セッションで実行）。
概念図
ヒント（クリックで段階的に開示）
ヒント1（方向性）
Day173-Q1 のプラグ DP（括弧 2 種＋端点につながる線 3）で、端点の数の上限を 2 から $2K$ に上げればよい。最後に $e=2m$ の値を読む。
ヒント2（アプローチ）
マス $(i,j)$ に入ってくる線（左 $a$、上 $b$）で場合分けする。
- 線なし: 新しい線の両端を下と右へ（
()）／ここを端点にして下か右へ 3 を出す（$e+1$）／1 マスだけの路（$e+2$） - 1 本だけ: 下か右へ延ばす／ここで終える（$e+1$）。3 なら路が完成、
()なら相方の括弧が 3 になる - 2 本:
(と)の組（同じ線の両端）は閉路なので禁止。3 と 3 は路が完成。3 と括弧は相方が 3 に。(()))(は Day171-Q3 と同じつなぎ替え
ヒント3（誘導）
- 値を
dict[状態] = 詰めた整数で持つ。$e$ が $d$ 増える遷移は(val << (80*d)) & mask（$e>2K$ の部分は切り捨て） - 1 行の終わりまで mod を取らず、行の頭で各 80 ビットの区画を取り出して mod を取る。区画は桁あふれしない（Step 4）
模範解答 (Python)
模範解答を表示する（まず自力で解いてから）
import sys
MOD = 998244353
S = 80 # 1 つの係数に使うビット数（行の終わりまで mod を取らない）
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 = int(data[0]), int(data[1]), int(data[2])
g = data[3:3 + h]
if w > h: # プロファイルの長さを短い辺にする
g = [''.join(g[i][j] for i in range(h)) for j in range(w)]
h, w = w, h
slots = 2 * k + 1 # 端点の数 e = 0..2k の係数を 1 つの整数に詰める
mask = (1 << (S * slots)) - 1
free = [[c == '.' for c in row] + [False] for row in g] + [[False] * (w + 1)]
def reduce(v):
r = 0
for t in range(slots):
r |= (((v >> (S * t)) & ((1 << S) - 1)) % MOD) << (S * t)
return r
# プラグ: 0 なし / 1 '(' / 2 ')' / 3 端点につながる線。位置 j は 2j ビット目
cur = {0: 1}
for i in range(h):
cur = {st << 2: reduce(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
v1 = (val << S) & mask # 端点が 1 つ増える
if a == 0 and b == 0:
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)) & mask) # 1 マスだけの路
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) + v1
else:
if a == 1 and b == 2:
continue # 同じ線の両端どうし: 閉路になるので禁止
if a == 3 and b == 3:
s2 = base # 路が 1 本完成
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: # a == 2 and b == 2
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))
print(' '.join(str((v >> (S * (2 * m))) & ((1 << S) - 1)) for m in range(1, k + 1)))
main()計算量: プロファイルの状態数を $S_w$（幅 5・6・7 で最大 264・858・2860、実測）とすると、マスごとに状態数ぶんの遷移と、括弧の相方探し $O(w)$、詰めた整数の加算 $O(K)$ ワード。全体 $O(HW\cdot S_w\cdot(w+K))$。$6\times30$、$K=20$ で 0.59〜0.74 s（Python 3.14.7、M1 MacBook Pro 8GB、負荷平均 2〜3 での実測、起動込み）。
Step-by-Step 解説
$W>H$ なら転置する。状態は 4 進で $w+1$ 個のプラグ（0 なし／1 (／2 )／3 端点につながる線）。行の頭で、右端のプラグが 0 の状態だけを 2 ビット左へずらす。
端点は「線がそのマスで終わる」たびに 1 つ数える。3 の線を作ったとき（始点）に $+1$、線を終えたとき（終点）に $+1$、1 マスの路は $+2$。3 と 3 が出会うマスは路の途中なので数えない。最後にすべてのプラグが 0 で $e=2m$ なら、路がちょうど $m$ 本。
相方は 3 を飛ばして括弧の深さを数える。( を終えると、その線のもう一方の端（相方の )）は「端点につながる線」になるので 3 に書き換える。(( の合流では 2 本目の ( の相方が ( に、)) では 1 本目の ) の相方が ) になる（Day171-Q3 と同じ）。
同じプロファイルの $e=0..2K$ の値をまとめて 1 つの整数 $\sum_e c_e 2^{80e}$ で持つ。遷移は「整数の足し算」と「左シフト＋マスク」だけになり、相方探しはプロファイル 1 つにつき 1 回で済む。1 マス進むごとに、全状態の区画の総和は高々 4 倍（1 つの状態から出る遷移は 4 本以下）。幅 7 で 1 行 $4^7=2^{14}$ 倍、状態数 $<2^{12}$、元の値 $<2^{30}$ なので区画は $2^{56}$ 未満に収まり、80 ビットで足りる。
キーを st << 6 | e にした版と出力が一致したうえで、$6\times30$、$K=10$ で 3.71 s → 0.70 s、$7\times30$ で 15.46 s → 2.08 s（実測）。
迷った他案と採らなかった理由
| 案 | 計算量 | 採否 | 理由 |
|---|---|---|---|
| 辺集合の全探索 | $O(2^{E})$ | 不採用 | 検証用。$4\times4$（24 辺）まで |
| キーに $e$ を含める（Day173-Q1 の拡張） | $O(HW S_w K w)$ | 不採用 | 正しいが、$6\times30$ で 3.71 s、$7\times30$ で 15.46 s（実測） |
| 値を長さ $2K+1$ のリストで持つ | 同上（定数が大） | 不採用 | Python のリスト加算はループになり、整数 1 回の加算より遅い（本セッションでは未計測） |
| 路の本数ではなく辺数で数え、最後に $m=\#\text{空き}-\#\text{辺}$ に読み替える | 同じ | 不採用 | 正しいが、辺数は最大 $HW$ まで伸びるので区画数が増える。端点の数なら $2K$ で打ち切れる |
| 端点の数ごとの値を 1 つの整数に詰める（本解） | $O(HW S_w (w+K))$ | 採用 | $6\times30$ で 0.59〜0.74 s |
前提が変わったら:
- $\min(H,W)=7$ なら $7\times30$ で 2.08 s（実測）。状態数 2860 を減らすには、括弧列を最小表現の番号付けにして状態を配列化する必要がある
- $K$ が $HW$ 程度（全部の本数）なら、区画数が増えて整数が長くなる。辺数で数える方が素直
- 路ではなく閉路も許す（2-因子＋路）なら、
()の合流を許す版になる。その場合は閉路の数も数えたくなるので、別の係数が要る
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
( と ) の合流を許す | Day171-Q3 の閉路の DP をそのまま使う | 400 盤面中 187 盤面で誤答（実測）。路だけを数えるなら禁止 |
| 1 マスだけの路を忘れる | 「路は辺を持つ」と思い込む | 400 盤面中 357 盤面で誤答（実測）。$e+2$ の遷移を足す |
| 3 と 3 の合流でも端点を数える | 端点を「出会い」で数える | 端点は線の始点と終点でだけ数える |
| 括弧の相方探しで 3 を括弧として数える | 3 は括弧の対応に入らない | 3 は飛ばして深さを数える |
| 詰めた整数を毎マス mod する | 区画ごとに取り出すので遅い | 行の頭で 1 回だけ。桁あふれしない理由は Step 4 |
次のステップ
- 発展1: 括弧列の最小表現で状態を番号付けし、$\min(H,W)=8$ まで広げる
- 発展2: 路と閉路の両方を許す「次数 2 以下の全域部分グラフ」を、路の本数と閉路の本数の 2 変数で数える
- 発展3: 端点の位置に条件をつける（例: 端点はすべて盤面の外周にある）
検証ログ（本セッションで実行した数値）
- 正解との照合（実測）: $H\le4$, $W\le5$（$HW\le16$）、壁の確率 0／0.1／0.25、$K\le10$ のランダム盤面で、辺集合の全探索（次数 2 以下・閉路なしの辺集合を数え、成分数 = マス数 − 辺数）と一致。キーに $e$ を含めた版で 800 盤面、本解（詰めた整数）で 400 盤面、不一致 0
- 誤った方法（実測、400 盤面）:
()の合流を許すと 187 盤面、1 マスの路を数えないと 357 盤面で誤答 - 既知の値との一致（実測）: $n\times n$ の $m=1$ が $n=1..7$ で 1, 4, 20, 276, 4324, 229348, 13535280（Day173-Q1 の出力と一致）。入力例 2 の輪は $\binom8m$ と一致
- 実行時間（実測、起動込み、本解／キーに $e$ を含めた版）: $5\times30$, $K=10$: 0.32 s／0.92 s、$6\times30$, $K=10$: 0.70 s／3.71 s、$6\times30$, $K=20$: 0.59〜0.74 s／7.67 s、$7\times30$: 2.08 s／15.46 s、$8\times10$: 2.38 s／15.72 s。$30\times6$ で壁 10%: 0.24 s。両版の出力は 5 盤面すべてで一致
- 状態数（実測）: 幅 5・6・7 でプロファイル最大 264・858・2860 個（$K$ によらない）
- 扱っていない範囲: 幅 7 以上、閉路を含む数え上げ、状態の配列化