bzoj2560串珠子——子集DP

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2560

转载：

---

很明显的状压dp 
一开始写的dp可能会出现重复统计的情况 而且难以去重 
假设 一个状态s的随意连边集合是A; 
那么 A应该是 全部合法的方案(Ans)+sigma(某一部分合法(即某一部分是连通图)的方案*其他任意连边的方案); 
那么可以把最终答案设置为f[i], 随意连边(也可以完全连边)设置成g[i]; 
先定一个基准点 x 和基准点相连的都是合法的, 其余集合 t=s^(1<<(x-1))可以随便连; 
f[i]=g[i]-sigma((t的所有子集i)f[i]*g[s^i]); 
为什么一个是f 一个是g 这样其实是要保证不重不漏

---

而且必须特别注意划分点一定是连通部分的，因为单个的点也算连通，但是这个“连通”会和随便连的方案混在一起(比如此时没有一个点相互连通的情况)；

但是确实有这样的情况，所以如果把划分点作为连通部分，那么这种方案只被算了一次，不会多算；

而若把划分点作为随便连部分，那么其他每个点都会有一次单独连通情况，就会多算了。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll const mod=1000000007;
ll n,a[20][20],f[1<<16],g[1<<16];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
    int m=(1<<n)-1;
    for(int s=1;s<=m;s++)
    {
        g[s]=1;
        for(int i=1;i<=n;i++)   if(s&(1<<(i-1)))
            for(int j=i+1;j<=n;j++)   if(s&(1<<(j-1)))
                (g[s]*=(a[i][j]+1))%=mod;
        f[s]=g[s];
        int nw;
        for(nw=n-1;;nw--)
            if(s&(1<<nw))break;
        nw=(s^(1<<nw));//去掉一个划分点 
        for(int k=nw;k;k=((k-1)&nw))//枚举nw的子集
            ((f[s]-=g[k]*f[s^k])+=mod)%=mod;//f和g别反 
    }
    printf("%lld",f[m]);
    return 0;
}