問題
$N$ 頂点 $M$ 辺の単純グラフ $G$ の彩色多項式 $P_G(k) = \sum c_i k^i$ の係数を求めよ。また $k = 10^9 + 7$ での値も mod で出力する。
制約
$2 \le N \le 18$
$0 \le M \le N(N-1)/2$
入出力例
入力例 1
3 3
0 1
1 2
0 2出力例 1
0 3 -3 1
2三角形は $k(k-1)(k-2) = k^3 - 3k^2 + 3k$。
ヒント (段階的開示)
ヒント1: 方向性
Whitney: $P_G(k) = \sum_{A \subseteq E} (-1)^{|A|} k^{c(A)}$。$M$ が大きい場合は頂点部分集合 DP を使う。
ヒント2: アプローチ
$P_G(k) = \sum_j s[j] \cdot k^{\underline{j}}$ で、$s[j]$ は $V$ を独立集合 $j$ 個に分割する方法の数。下降階乗を標準基底に変換するため Stirling 数 (1st kind) を使う。
ヒント3: 誘導
部分集合 DP:
dp[S][j] = $S$ を $j$ 個の独立集合に分割する数。最小元を含む独立集合の選び方で遷移。模範解答 (Python, N≤18 版)
import sys
input = sys.stdin.readline
def solve():
N, M = map(int, input().split())
adj = [[False] * N for _ in range(N)]
for _ in range(M):
u, v = map(int, input().split())
adj[u][v] = adj[v][u] = True
MOD = 10**9 + 7
indep = [True] * (1 << N)
for mask in range(1 << N):
ok = True
for u in range(N):
if not (mask >> u & 1):
continue
for v in range(u + 1, N):
if (mask >> v & 1) and adj[u][v]:
ok = False; break
if not ok: break
indep[mask] = ok
min_v = [0] * (1 << N)
for mask in range(1, 1 << N):
min_v[mask] = (mask & -mask).bit_length() - 1
dp = [[0] * (N + 1) for _ in range(1 << N)]
dp[0][0] = 1
for mask in range(1, 1 << N):
mv = min_v[mask]
t = mask
seen = set()
while True:
if (t >> mv & 1) and indep[t] and t not in seen:
seen.add(t)
rest = mask ^ t
for j in range(N):
if dp[rest][j]:
dp[mask][j + 1] += dp[rest][j]
if t == 0:
break
t = (t - 1) & mask
full = (1 << N) - 1
s = dp[full]
s1 = [[0] * (N + 1) for _ in range(N + 1)]
s1[0][0] = 1
for j in range(1, N + 1):
for i in range(j + 1):
if i > 0:
s1[j][i] += s1[j-1][i-1]
s1[j][i] -= (j - 1) * s1[j-1][i]
coef = [0] * (N + 1)
for j in range(N + 1):
if s[j] == 0:
continue
for i in range(j + 1):
coef[i] += s[j] * s1[j][i]
print(*coef)
k = MOD
result = 0
k_pow = 1
for i in range(N + 1):
result = (result + coef[i] % MOD * k_pow) % MOD
k_pow = k_pow * k % MOD
print(result % MOD)
solve()Step-by-Step 解説
1Whitney の定理
$P_G(k) = \sum_{A \subseteq E} (-1)^{|A|} k^{c(A)}$。辺が多い場合は使えない。
$P_G(k) = \sum_{A \subseteq E} (-1)^{|A|} k^{c(A)}$。辺が多い場合は使えない。
2独立集合分解
$P_G(k) = \sum_j s[j] k^{\underline{j}}$。部分集合 DP で各 $S$ を独立集合に分割する方法を数える。
$P_G(k) = \sum_j s[j] k^{\underline{j}}$。部分集合 DP で各 $S$ を独立集合に分割する方法を数える。
3Stirling 数による変換
$k^{\underline{j}} = \sum_i S_1(j, i) k^i$（符号付き第1種）で標準基底に変換。
$k^{\underline{j}} = \sum_i S_1(j, i) k^i$（符号付き第1種）で標準基底に変換。
4評価
$k = 10^9 + 7$ で mod 計算。
$k = 10^9 + 7$ で mod 計算。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| Stirling 数の符号 | 第1種・2種の混同 | $s_1[j][i] = s_1[j-1][i-1] - (j-1) s_1[j-1][i]$ |
| 部分集合列挙が遅い | 素朴 $O(4^N)$ | t = (t-1) & mask で $O(3^N)$ |
| 独立集合判定が遅い | 全辺チェック | 前処理で indep[mask] |
次のステップ
- 複数 k 評価 + ラグランジュ補間
- Tutte 多項式（彩色多項式の一般化）