AK-dream

题目描述

铭铭有 $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];
//f:可以不联通 g:必须联通

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;
}

 评论