問題
$N$ 頂点 $M$ 辺のグラフ $G$ が与えられる（$N \le 20$）。各頂点 $v$ は確率 $p_v$ で独立にアクティブになる。
アクティブな頂点集合 $S$ が独立集合（$S$ 内に辺がない）である確率を $\bmod 998244353$ で求めよ。
さらに $Q$ 個のクエリ $v$ に対し、「頂点 $v$ がアクティブかつ $S$ が独立集合である」確率も求めよ。
制約
| パラメータ | 範囲 |
|---|---|
| $N$ | $1 \le N \le 20$ |
| $M$ | $0 \le M \le N(N-1)/2$ |
| $Q$ | $1 \le Q \le N$ |
| $p_v$ | 分数で与えられる（分母 $\le 10^9$） |
| 時間制限 | 3秒 |
入出力例
入力例 1
3 2 1
1 2
1 2
1 2
1 2
2 3
1出力例 1
499122177
499122178$p_1=p_2=p_3=1/2$、辺は 1-2, 2-3。IS の確率 = $3/8 \bmod p$、頂点1がアクティブかつIS = $1/4 \bmod p$。
概念図: ビット DP による独立集合の列挙
ヒント（段階的開示）
ヒント1: 方向性
$N \le 20$ なので $2^N \le 10^6$ の全部分集合を列挙できる。各部分集合 $S$ が独立集合かどうかをビット DP で前処理し、各独立集合の確率を足し合わせる。
ヒント2: アプローチ
- 独立集合判定（前処理）:
is_indep[0] = True、$S$ の最下位ビット $v$ についてis_indep[S] = is_indep[S^(1<<v)] and not (adj_mask[v] & (S^(1<<v))) - 確率計算: $P(S) = \prod_{v \in S} p_v \cdot \prod_{v \notin S} (1-p_v)$ を $\bmod p$ で計算
- 答え: 全独立集合の $P(S)$ の和
- 条件付き: $v$ がビット $v$ を持つ独立集合のみ足し込む
ヒント3: 実装骨格
size = 1 << N
is_indep = [False]*size; is_indep[0] = True
for S in range(1, size):
v = (S & -S).bit_length() - 1 # 最下位ビット位置
rest = S ^ (1 << v)
is_indep[S] = is_indep[rest] and not (adj_mask[v] & rest)
total = 0
conditional = [0]*N
for S in range(size):
if not is_indep[S]: continue
pr = 1
for v in range(N):
pr = pr * (p[v] if S&(1<模範解答 (Python)
import sys
input = sys.stdin.readline
MOD = 998244353
def modinv(a, m=MOD): return pow(a, m-2, m)
def solve():
N, M, Q = map(int, input().split())
p = []; q = []
for _ in range(N):
num, den = map(int, input().split())
pv = num * modinv(den) % MOD
p.append(pv); q.append((1-pv)%MOD)
adj_mask = [0]*N
for _ in range(M):
u, v = map(int, input().split())
u -= 1; v -= 1
adj_mask[u] |= (1<Step-by-Step 解説
1独立集合の高速列挙（ビット DP）
$\text{is\_indep}[S]$：$S$ の最下位ビット $v$ を除いた部分集合 $S' = S \setminus \{v\}$ が独立集合、かつ $v$ が $S'$ 内の頂点と非隣接、の両方が成立するとき TRUE。$O(2^N)$。
$\text{is\_indep}[S]$：$S$ の最下位ビット $v$ を除いた部分集合 $S' = S \setminus \{v\}$ が独立集合、かつ $v$ が $S'$ 内の頂点と非隣接、の両方が成立するとき TRUE。$O(2^N)$。
2各独立集合の確率（mod 逆元）
$P(S) = \prod_{v \in S} p_v \cdot \prod_{v \notin S} (1-p_v)$。分数は mod 逆元で整数に変換。
$P(S) = \prod_{v \in S} p_v \cdot \prod_{v \notin S} (1-p_v)$。分数は mod 逆元で整数に変換。
3総和の計算
全独立集合 $S$ について $P(S)$ を足し合わせる。条件付き確率は $v \in S$ のときのみ加算。
全独立集合 $S$ について $P(S)$ を足し合わせる。条件付き確率は $v \in S$ のときのみ加算。
4最下位ビット位置の計算
(S & -S) で最下位ビットを取り出し、.bit_length() - 1 でゼロ始まりのビット位置を得る。
計算量
独立集合前処理: $O(2^N)$
確率計算: $O(2^N \cdot N)$
全体: $O(2^N \cdot N)$（$N=20$ で $\approx 2 \times 10^7$、十分高速）
空間: $O(2^N + N)$
確率計算: $O(2^N \cdot N)$
全体: $O(2^N \cdot N)$（$N=20$ で $\approx 2 \times 10^7$、十分高速）
空間: $O(2^N + N)$
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 最下位ビット位置計算の誤り | bin(S&-S).count('0') では誤り | (S & -S).bit_length() - 1 |
| 確率の積で浮動小数点を使う | 精度誤差で答えが変わる | mod 逆元で整数計算 |
| $q_v = 1-p_v$ の計算で負になる | Python の mod 演算は負を返さないが念のため | (1-pv) % MOD |
| 辺の入力で 1-indexed を 0-indexed に変換しない | adj_mask の参照がズレる | u -= 1; v -= 1 |
次のステップ
- 発展問題: 独立集合の個数を mod p で数え上げ（包除原理 + 頂点被覆数）
- 関連: Profile DP（行ごとのビット集合 DP、グリッドグラフ）
- 応用: 最大独立集合数 $\alpha(G)$ の計算（Bron-Kerbosch や分割統治）