题目描述
铭铭有$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; }
|