問題
$N \times N$ の0/1行列 $A$ について、パーマネント
$$ \mathrm{perm}(A) = \sum_{\sigma \in S_N} \prod_{i=1}^{N} A_{i,\sigma(i)} $$
を $\bmod\ 10^9+7$ で求めよ。これは行 $i$・列 $j$ を $A_{ij}=1$ で結ぶ二部グラフの完全マッチング総数に等しい。
制約
$1 \le N \le 20$
$A_{ij} \in \{0, 1\}$
$\bmod\ 10^9+7$
時間制限: 2sec
入出力例
入力例 1
3
1 1 0
0 1 1
1 0 1出力例 1
2概念図: Ryser の公式（列集合の包除）
ヒント（段階的開示）
ヒント1: 方向性
定義通りは $N!$ で $N=20$ は不可能。行列式と違いガウス消去（多項式時間）は使えない（perm計算は #P困難）。Ryser の公式で $O(2^N N)$ に落とせる。
ヒント2: アプローチ
$$ \mathrm{perm}(A) = (-1)^N \sum_{S \subseteq \{1,\dots,N\}} (-1)^{|S|} \prod_{i} \Big( \sum_{j \in S} A_{ij} \Big) $$
列の部分集合 $S$ を全列挙し、各行の「$S$ 内の列の和」を掛け合わせる。符号は $|S|$ の偶奇。
ヒント3: 誘導
Gray code で $S$ を1要素ずつ変化させ、各行の「$S$ 内の列和」を差分更新すれば定数時間で維持できる。素朴でも $O(2^N N) \approx 2\times10^7$ で間に合う。空集合は積0なので寄与なし。
模範解答 (Python)
import sys
def solve():
data = sys.stdin.buffer.read().split()
idx = 0
N = int(data[idx]); idx += 1
MOD = 10**9 + 7
rows = []
for i in range(N):
mask = 0
for j in range(N):
if int(data[idx]) == 1:
mask |= (1 << j)
idx += 1
rows.append(mask)
row_sum = [0]*N
result = 0
sign = 1
prev = 0
full = 1 << N
for g in range(1, full):
gray = g ^ (g >> 1)
diff = gray ^ prev
bit = diff.bit_length() - 1
col = 1 << bit
if gray & diff: # 列 bit を追加
for i in range(N):
if rows[i] & col:
row_sum[i] += 1
sign = -sign
else: # 列 bit を除去
for i in range(N):
if rows[i] & col:
row_sum[i] -= 1
sign = -sign
prev = gray
prod = 1
for i in range(N):
prod = (prod * row_sum[i]) % MOD
if prod == 0:
break
if prod:
result = (result + sign * prod) % MOD
if N & 1:
result = (-result) % MOD
print(result % MOD)
solve()
Step-by-Step 解説
1perm と #P困難性
行列式は符号付きで打ち消しがあり多項式時間だが、perm は符号がなく Valiant により #P困難。多項式時間アルゴリズムは未知。
行列式は符号付きで打ち消しがあり多項式時間だが、perm は符号がなく Valiant により #P困難。多項式時間アルゴリズムは未知。
2Ryser の公式
包除原理で $\mathrm{perm}(A)=(-1)^N\sum_S(-1)^{|S|}\prod_i(\sum_{j\in S}A_{ij})$。列集合の全列挙で $O(2^N N)$。
包除原理で $\mathrm{perm}(A)=(-1)^N\sum_S(-1)^{|S|}\prod_i(\sum_{j\in S}A_{ij})$。列集合の全列挙で $O(2^N N)$。
3行集合和の意味
$\sum_{j\in S}A_{ij}$ は行 $i$ が $S$ 内に持つ1の個数。全行の積は割当の場合の数で、包除で重複を打ち消すと順列割当（完全マッチング）が残る。
$\sum_{j\in S}A_{ij}$ は行 $i$ が $S$ 内に持つ1の個数。全行の積は割当の場合の数で、包除で重複を打ち消すと順列割当（完全マッチング）が残る。
4Gray code 高速化
$S$ を Gray code 順に列挙すると隣接 $S$ は1列だけ変化。
$S$ を Gray code 順に列挙すると隣接 $S$ は1列だけ変化。
row_sum を $O(N)$ で差分更新でき、主コストは積計算 $O(2^N N)$。
5符号と mod
$(-1)^{|S|}$ を
$(-1)^{|S|}$ を
sign で管理、最後に $(-1)^N$ を掛ける。負値は % MOD で正規化。
計算量
Ryser (Gray code): $O(2^N N)$
$N=20$: $2^{20}\cdot 20 \approx 2\times 10^7$
空間: $O(N)$
定義通り $O(N!)$ は不可能
$N=20$: $2^{20}\cdot 20 \approx 2\times 10^7$
空間: $O(N)$
定義通り $O(N!)$ は不可能
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 定義通り $N!$ 計算 | 全順列DFS | Ryser $O(2^N N)$ |
| 行列式のガウス消去を流用 | permは消去不可 | 包除原理を使う |
| 符号 $(-1)^N$ 忘れ | 公式の前因子 | 最後にNの偶奇で調整 |
| mod で負値放置 | sign*prod が負 | (x%MOD+MOD)%MOD |
| 空集合を含める | 積0だが符号が乱れる | $S=\emptyset$ はスキップ |
次のステップ
- 発展問題: 非0/1行列のperm、bitDPによる完全マッチング数え上げ $O(2^N N)$
- 類題: 二部グラフ完全マッチング数、割当数え上げ
- 応用: ボソンサンプリング（量子計算）、統計力学の分配関数