[清华集训2012] 串珠子
题意
给定 \(n\) 个点和 \(n\times n\) 的矩阵 \(c\)。
有 \(c_{i,j}\) 种方案把点 \(i\) 和点 \(j\) 连接起来。
求有多少种方案使得整张图连通。
思路
注意到 \(1\le n \le 16\)，考虑状压。
定义 \(g_i\) 为集合 \(i\) 的连边方案数，有
\[g_i=\prod_{u,v \in i} (c_{u,v}+1) \]即 \((u,v)\) 有 \(c_{i,j}\) 种方案连，有一种方案不连。
定义 \(f_i\) 为集合 \(i\) 连通时的方案数，有
\[f_i=g_i-\sum_{j \subset i} g_j\times f_{C j} \]其中 \(C\) 是补集符号。
即枚举不连通的情况减去，枚举不连通的子集，
不连通子集连边的方案数乘上补集连通的方案数就是总方案数。
实现时注意固定 \(i\) 中的一个数，这样才能不重不漏。
答案为 \(f_{2^n-1}\)。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 20;
int n, c[N][N];
ll f[1 << N], g[1 << N];
const int mod = 1e9 + 7;
int main() {
cin >> n;
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
cin >> c[i][j];
for (int i = 0; i < (1 << n); i ++) {
g[i] = 1;
for (int j = 0; j < n; j ++)
if (i >> j & 1) for (int k = j + 1; k < n; k ++)
if (i >> k & 1)
g[i] = g[i] * (c[j][k] + 1) % mod;
}
for (int i = 0; i < (1 << n); i ++) {
int I = i ^ (i & (-i));
f[i] = g[i];
for (int j = I; j; j = (j - 1) & I) {
f[i] = f[i] - g[j] * f[i ^ j];
f[i] = (f[i] % mod + mod) % mod;
}
}
cout << f[(1 << n) - 1] << "\n";
return 0;
}