bzoj2560串珠子—

题目：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=;

ll n,a[][],f[<<],g[<<];

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

            scanf("%d",&a[i][j]);

    int m=(<<n)-;

    for(int s=;s<=m;s++)

    {

        g[s]=;

        for(int i=;i<=n;i++)   if(s&(<<(i-)))

            for(int j=i+;j<=n;j++)   if(s&(<<(j-)))

                (g[s]*=(a[i][j]+))%=mod;

        f[s]=g[s];

        int nw;

        for(nw=n-;;nw--)

            if(s&(<<nw))break;

        nw=(s^(<<nw));//去掉一个划分点

        for(int k=nw;k;k=((k-)&nw))//枚举nw的子集

            ((f[s]-=g[k]*f[s^k])+=mod)%=mod;//f和g别反

    }

    printf("%lld",f[m]);

    return ;

}

巴特西

bzoj2560串珠子——子集DP

最新文章

热门文章