問題
$N$ 頂点 $M$ 辺の単純無向グラフ $G$ が与えられる。辺の部分集合 $F\subseteq E$ であって、グラフ $(V,F)$（頂点は全部残し、辺は $F$ だけ）が 連結 になるものの個数を $998244353$ で割った余りを求めよ。
入力形式
N M
u_1 v_1
...
u_M v_M制約
| # | 条件 |
|---|---|
| 1 | $1\le N\le 15$ |
| 2 | $0\le M\le N(N-1)/2$ |
| 3 | $1\le u_i<v_i\le N$、同じ辺は 2 度現れない |
| 4 | 入力はすべて整数 |
入出力例
入力例1
3 3
1 2
2 3
1 3出力例1
4（2 辺を選ぶ 3 通り＋3 辺全部の 1 通り）
入力例2
4 5
1 2
2 3
3 4
4 1
1 3出力例2
14（5 辺全部 1 通り、4 辺 5 通り（どの 1 辺を抜いても連結）、3 辺は $\binom53=10$ 通りから三角形 2 つを除いた 8 通り）
入力例3
4 2
1 2
3 4出力例3
0背景と出典
連結な全域部分グラフの個数は Tutte 多項式の値 $T_G(1,2)$ に等しい（Tutte 多項式の標準的な性質。本セッションでは文献を開いていない）。また各辺が独立に確率 $1/2$ で生き残るとき $G$ が連結のままである確率は「本問の答え $/2^M$」で、これは通信網の 全端末信頼度（all-terminal reliability） の $p=1/2$ の場合にあたる。一般の $p$ でも同じ DP の $2^{e}$ を $\prod$ に置き換えれば計算でき、信頼度の厳密計算が #P 困難であることから、小さい $N$ での厳密解として実務の検算に使われる型である。
完全グラフ $K_n$ での答えは「$n$ 頂点のラベル付き連結グラフの数」（OEIS A001187: 1, 1, 4, 38, 728, 26704, 1866256, 251548592, 66296291072, 34496488594816, …）。本セッションでは OEIS を開いておらず、この列は記憶している値で、本解の出力（$n=1..10$）と一致した。
概念図：最小頂点を含む成分で分類
ヒント（クリックで段階的に開示）
ヒント1（方向性）
頂点集合 $S$ ごとに「$S$ の中の辺だけで $S$ を連結にする辺集合の数」$f(S)$ を求める。「$S$ の中の辺の選び方すべて」は $2^{e(S)}$ 通り（$e(S)$ は両端が $S$ に入る辺の本数）。
ヒント2（アプローチ）
$2^{e(S)}$ から連結でないものを引く。連結でない辺集合を分類するのに、$S$ の最小の頂点 $v$ を含む連結成分 $T$ に注目する。$T$ が決まれば、$T$ の中は連結（$f(T)$ 通り）、$S\setminus T$ の中は何でもよい（$2^{e(S\setminus T)}$ 通り）、$T$ と $S\setminus T$ の間の辺は使わない。
ヒント3（誘導）
$$f(S)=2^{e(S)}-\sum_{\substack{v\in T\subsetneq S}}f(T)\cdot2^{e(S\setminus T)}\qquad(v=\min S)$$
$T$ は「$v$ を含み $S$ と等しくない $S$ の部分集合」を列挙する。$S$ から $v$ を除いた $R$ の部分集合 $\mathit{sub}$ を sub = (sub - 1) & R で回し、$T=\mathit{sub}\cup\{v\}$ とする。
模範解答 (Python)
模範解答を表示する（まず自力で解いてから）
import sys
MOD = 998244353
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [0] * n
for i in range(m):
u, v = int(data[2 + 2 * i]) - 1, int(data[3 + 2 * i]) - 1
adj[u] |= 1 << v
adj[v] |= 1 << u
full = 1 << n
# e[S]: 両端が S に入る辺の本数（最小の頂点 v を抜いた集合から、v と S の間の辺を足す）
e = [0] * full
for S in range(1, full):
v = (S & -S).bit_length() - 1
e[S] = e[S & (S - 1)] + bin(adj[v] & S).count("1")
pw = [1] * (m + 1)
for i in range(1, m + 1):
pw[i] = pw[i - 1] * 2 % MOD
# f[S]: S の中の辺だけで S を連結にする辺集合の数
f = [0] * full
for S in range(1, full):
low = S & -S
R = S ^ low # T は low を必ず含む。残り R の部分集合 sub で T = sub | low
if R == 0:
f[S] = 1 # 1 頂点は辺なしで連結
continue
acc = 0
sub = (R - 1) & R # sub = R（T = S）は除く
while True:
T = sub | low
acc += f[T] * pw[e[S ^ T]]
if sub == 0:
break
sub = (sub - 1) & R
f[S] = (pw[e[S]] - acc) % MOD
print(f[full - 1])
main()計算量: 各 $S$ で $2^{|S|-1}-1$ 個の $T$ を見るので合計 $\sum_S 2^{|S|-1}\approx3^N/2$、つまり $O(3^N)$。実測（Python 3.14.7、M1 Mac）で $K_{15}$（$M=105$）が 0.89 s、$K_{14}$ が 0.29 s、$K_{16}$ が 2.40 s。
Step-by-Step 解説
$S$ の中の辺を好きに選ぶ方法は $2^{e(S)}$ 通り。そのうち $S$ が連結になるものが $f(S)$、ならないものを数えて引く。
辺集合を 1 つ決めると、最小の頂点 $v$ を含む連結成分 $T$ はただ 1 つに決まる。連結でないとは $T\ne S$ ということ。
逆に $T$（$v\in T\subsetneq S$）を決めたとき、「$v$ の成分がちょうど $T$」になる辺集合は
- $T$ の中: $T$ を連結にする $f(T)$ 通り
- $S\setminus T$ の中: 何でもよい $2^{e(S\setminus T)}$ 通り
- $T$ と $S\setminus T$ の間: 1 本も使わない（使うと成分が $T$ より大きくなる）
の積。各辺集合はちょうど 1 つの $T$ で数えられるので、重複なく引ける。
「どれか 1 つの成分 $T$」で分類すると、成分が 3 個ある辺集合はどの成分を $T$ に選ぶかで 3 回引かれる。固定しない版は検算 300 件中 190 件で誤った（実測）。
$S$ の最小の頂点 $v$ を抜いた集合 $S'$ について $e(S)=e(S')+|\mathrm{adj}(v)\cap S|$。隣接をビット列で持てば popcount 1 回。
sub = (sub - 1) & R は $R$ の部分集合を大きい順にすべて回す定番。$\mathit{sub}=R$（$T=S$）は最初に除き、$\mathit{sub}=0$（$T=\{v\}$）で止める。
迷った他案と採らなかった理由
| 案 | 計算量 | 採否 | 理由 | ||
|---|---|---|---|---|---|
| 辺集合を全部試して Union-Find | $O(2^M\cdot M)$ | 検算用のみ | $K_{15}$ で $2^{105}$。$M\le13$ の検算に使った | ||
| 最小の頂点を固定しない包除 | $O(3^N)$ | 不採用 | 成分が 3 個以上ある辺集合を重複して引く（300 件中 190 件誤答、実測） | ||
| 削除縮約 $T_G=T_{G-e}+T_{G/e}$ で Tutte 多項式を再帰 | 最悪 $O(2^M)$、メモ化してもグラフの形が多い | 不採用 | 密なグラフで爆発する。本問は頂点数が小さいので頂点集合の DP が有利 | ||
| 指数型母関数の $\log$（完全グラフ限定） | $O(N\log N)$ | 不採用 | $K_n$ のように辺の数が $ | S | $ だけで決まる場合にしか使えない。一般のグラフには使えない |
| 最小頂点固定の $O(3^N)$ DP（本解） | $O(3^N)$ | 採用 | 全探索 300 件・$K_n$（$n\le10$）の既知の値と一致 |
前提が変わったら:
- 各辺が確率 $p$ で生き残る信頼度 なら、$2^{e(S)}$ を「$S$ の中の辺をどう選んでも」の確率 1 に、$2^{e(S\setminus T)}$ も 1 に、「$T$ と外の間の辺を使わない」確率 $(1-p)^{\mathrm{cut}(T,S\setminus T)}$ を掛ける形に書き換える（漸化式 $R(S)=1-\sum R(T)(1-p)^{\mathrm{cut}}$）
- $N$ が 20 前後 なら $3^{20}\approx3.5\times10^9$ で無理。部分集合畳み込み（ranked zeta）で $O(2^NN^2)$ にする
- 連結な誘導部分グラフ（頂点を選ぶ） を数えるなら別問題。頂点集合ごとに「$S$ の誘導部分グラフが連結か」を BFS で判定する方が簡単
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 最小の頂点を含む成分に限定しない | 分類の一意性を確かめていない | $T\ni\min S$ に固定（300 件中 190 件誤答） |
| $T=S$ も引いてしまう | 部分集合列挙の開始点を $R$ にする | sub = (R - 1) & R から始める |
| $f(\{v\})$ を 0 にする | 「辺が無い＝連結でない」と思い込む | 1 頂点は辺なしで連結（$f=1$）。$N=1$ の答えは 1 |
| $T$ と $S\setminus T$ の間の辺も自由にする | 成分の定義の読み落とし | 間の辺は使わない（掛けない） |
次のステップ
- 発展1: 答えを辺数ごとに求める（「辺を $j$ 本使って連結」の個数）。$2^{e}$ を $(1+y)^{e}$ の多項式に置き換える
- 発展2: 同じ枠組みで「2 辺連結な全域部分グラフ」の数を数えるにはどんな分類が要るか考える
- 次回予告: 焦点帯 M1 を続ける
検証ログ（本セッションで実行した数値）
- 全探索との一致（実測）: $N\le7$、辺 13 本以下のランダムグラフ 300 件（答えが 0 のもの 121 件）で、辺集合 $2^M$ 通りを Union-Find で調べた結果とプログラム全体の出力が全件一致
- 完全グラフ（実測）: $K_1..K_8$ で 1, 1, 4, 38, 728, 26704, 1866256, 251548592。法を $10^{60}$ にした版で $K_9$=66296291072、$K_{10}$=34496488594816。記憶している OEIS A001187 の値と一致
- 最小頂点を固定しない版（実測）: 同じ 300 件中 190 件で誤答
- 実行時間（実測）: $K_{14}$ 0.29 s、$K_{15}$ 0.89 s、$K_{16}$ 2.40 s。$N\le15$ にした
- 扱っていない範囲: 確率 $p$ の信頼度版の実装、部分集合畳み込みによる $O(2^NN^2)$ 版、Tutte 多項式の文献との照合