题目描述
铭铭有$n$个十分漂亮的珠子和若干根颜色不同的绳子。现在铭铭想用绳子把所有的珠子连成一个整体。
现在已知所有的珠子互不相同，用整数$1$到$n$编号。对于第$i$个珠子和第$j$个珠子，可以选择不用绳子连接，或者在$c_{i,j}$根不同颜色的绳子中选择一根将它们连接。如果把珠子看作点，把绳子看作边，将所有珠子连成一个整体即为所有点构成一个连通图。特别地，珠子不能和自己连接。
铭铭希望知道总共有多少种不同的方案将所有珠子连成一个整体。由于答案可能很大，因此只需输出答案对$1000000007$取模的结果。
输入格式
输入第一行包含一个正整数$n$，表示珠子的个数。接下来$n$行，每行包含$n$个非负整数，用空格隔开。这$n$行中，第$i$行第$j$个数为$c_{i,j}$。
输出格式
输出一行一个整数，为连接方案数对$1000000007$取模的结果。
$n\le 20$
题解
状压DP
首先我们设$f[S]$表示：$S$中包含的珠子两两之间任意连边(可以不连)的方案数
显然，$f[S]=\Pi_{i\in S,j\in S} (c[i][j]+1)$
这个可以在$O(2^nn^2)$的时间内预处理
但是这样求出的方案，不一定保证每个方案都是一个连通图
所以我们要再进行一次DP
设$g[S]$表示：$S$中包含的珠子两两之间任意连边(可以不连)，且构成一个连通块的方案数
初始时我们先把每个$g[S]$赋值成$f[S]$，然后再删除掉不合法的部分
我们考虑$1$这颗珠子，在一个不合法的方案中，一定有部分珠子和$1$不在同一个连通块内
所以对于每个$g[S]$，我们枚举$S$的一个不含珠子$1$的子集$S_2$，表示$S_2$中的那些珠子和$1$不在同一个连通块内
这样的方案数有多少？首先，$S_2$内的珠子不一定要形成一整个连通块，所以是$f[S_2]$
其次，$S-S_2$即与$1$连通的珠子一定在一个连通块内，所以是$g[S-S_2]$
所以不合法的方案有$f[S_2]*g[S-S_2]$种，从$g[S]$中减去
所以我们可以得到：$g[S]=f[S]-\sum f[S_2]*g[S-S_2]$($S_2$是$S$的所有不含珠子$1$的子集)
答案即为$g[2^n-1]$
p.s. 我们发现所有的$S-S_2$都是含有珠子1的，所以为了降低复杂度，我们可以不去求那些不含珠子$1$的$g[S]$
时间复杂度为枚举子集复杂度$O(3^n)$但是大大小于这个上界
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline void read(T &num) {
T x = 0, ff = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') ff = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
num = x * ff;
}
const ll mod = 1000000007;
int n;
ll a[30][30], f[1050005], g[1050005];
inline ll fpow(ll x, ll t) {
ll ret = 1;
for (; t; t >>= 1, x = x * x % mod) if (t & 1) ret = ret * x % mod;
return ret;
}
int main() {
read(n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
read(a[i][j]);
}
}
for (int s = 0; s <= (1 << n) - 1; s++) {
f[s] = 1;
for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) {
if (((s>>(i-1))&1) && ((s>>(j-1))&1)) {
f[s] = f[s] * (a[i][j] + 1) % mod;
}
}
}
memcpy(g, f, sizeof(g));
for (int s = 1; s <= (1 << n) - 1; s++) {
if (!(s & 1)) continue;
for (int s2 = (s - 1) & s; s2; s2 = (s2 - 1) & s) {
if (!(s2 & 1)) continue;
g[s] = (g[s] - g[s2] * f[s-s2] % mod + mod) % mod;
}
}
printf("%lld\n", g[(1<<n)-1]);
return 0;
}
|
