P5933 [清华集训2012] 串珠子 题解
Link
非常好的一道状压题目（为啥自己总是想不到呢……）。
首先我们发现 \(n\) 很小，于是考虑状压。我们一开始肯定会设 \(dp_s\) 为集合 \(s\) 内的点相互连通的方案数。但是，我们发现，这个东西非常不好算，而且难以转移。于是……
\(\Huge{补集!}\)
没错，内部点连边的方案数很显然，我们只需要算出内部点不连通的方案，然后减走就行了。
其实，我们发现，内部连通的方案数之所以难算，就是因为只需要一条边就可以连通，方案之间的界限是模糊的；而如果不连通，我们只需要规定哪两部分不连通就行了。
因此，我们有了这样一个方案。我们现在要计算 \(s\) 的答案 \(dp_s\)，那么就从一个点开始，不断扩展点集（或者更准确的说，去枚举包含这个点的点集），答案就是这个点集内部连通的方案数与他在 \(s\) 中的补集的连边方案数。这样做的含义就是，保证一个点集内部连通，然后割断它与其补集的连边，补集内部随意连边。我们来考虑这样做的正确性。每次扩展（或更换）点集都是在增加强制连通的点，而这些点与点集之外都是强制割裂的，也就是说，只要这些点集不重复，那么他们与外界的联系也是不重复的，最终结果也是不会重复的。
关于具体实现，首先要钦定一个点 \(p \in s\)，并枚举 \(p\) 在 \(s\) 中的补集 \(C_sp\) (\(C\) 为补集符号）的子集 \(subs\)，有 \(dp_s = \sum_{subs \in C_sp} f_{subs} \times dp_{C_ssubs}\)。这里需要注意，\(subs\) 与 \(C_ssubs\) 的位置不能互换，因为这里的 \(p\) 点就是最初的基准点，\(C_ssubs\) 是围绕这一点不断变化和扩展的，如果交换，则会算重。这里建议通过小样例手动模拟一下来理解。
代码（蛮乱的）：
#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
const int N = 20;
const int NN = 70000;
inline int read(){
int x = 0; char ch = getchar();
while(ch<'0' || ch>'9') ch = getchar();
while(ch>='0'&&ch<='9') x = x*10+ch-48, ch = getchar();
return x;
}
inline int fpow(int a, int b){
int ret = 1;
a%=mod;
while(b){
if(b & 1){
ret = (1ll*ret*a)%mod;
}
a = (1ll*a*a)%mod;
b>>=1;
}
return ret;
}
int c[N][N];
int n;
int f[NN];
int dp[NN];
int main(){
n = read();
for(int i = 1; i<=n; ++i){
for(int j = 1; j<=n; ++j){
c[i][j] = read();
}
}
for(int s = 1; s<=(1<<n)-1; ++s){
f[s] = 1;
for(int i = 1; i<=n; ++i){
if((s>>(i-1))&1){
for(int j = i+1; j<=n; ++j){
if((s>>(j-1))&1){
f[s] = (1ll*(c[i][j]+1)*f[s])%mod;
}
}
}
}
}
for(int s = 1; s<=(1<<n)-1; ++s){
int tmp;
// for(int i = 1; i<=n; ++i){
// if((s>>(i-1))&1){
// tmp = (1<<(i-1));
// break;
// }
// }
for(int i = n; i>=1; --i){
if((s>>(i-1))&1){
tmp = (1<<(i-1));
break;
}
}
int ts = s^tmp;
int Cs = 0;
for(int subs = ts; subs; subs = ts&(subs-1)){
Cs = (1ll*Cs+1ll*f[subs]*dp[s^subs]%mod)%mod;
}
// cout << Cs << " ";
dp[s] = ((f[s]-Cs)%mod+mod)%mod;
// Cs = 0;
// for(int subs = ts; subs; subs = ts&(subs-1)){
// Cs = (1ll*Cs+1ll*f[s^subs]*dp[subs]%mod)%mod;
// }
// cout << Cs << endl;
}
printf("%d\n", dp[(1<<n)-1]);
return 0;
}