【2016NOIP十连测】【test4】【状压DP】【容斥原理】巨神兵

题目大意：

　　给一个n个点(n<=17)，m条边的有向图（无自环、无重边），求其无环子图的方案数。

题解：

　　看到n<=17，显然是用状压dp。

　　用f[i]表示点集i的满足条件的方案数。

　　状态转移时可以一层一层地把点加进点集。

　　具体的，枚举已知点集i，在i的补集中枚举下一层的点集j（可以无边相连）（以下i,j定义相同），

　　统计由i连向j的边e。对于这些边，每一条都可以选或不选，

　　就有2^e种情况，即:

　　　　f[i^j]+=f[i]*2^e;

　　这显然是错误的，

　　因为对于点集k的一种连边方案，可以有多种方式划分成i,j,

　　这就意味着不同的i,j可能包含了同样的方案。

　　于是以j中包含的元素把并集为k的i和j分类

　　转移的时候多乘个容斥系数就可以了，即：

　　　　f[i^j]+=f[i]*2^e*(-1)^size(j)+1;

　　复杂度O(3ⁿm)可优化成O(3ⁿ+2ⁿm);

#include<cstdio>

#include<iostream>

using namespace std;

typedef long long ll;

const int N = ;

const int M = ;

const int P = 1e9+;

ll read(){

    ll re=;bool neg=;char ch=getchar();

    while (!isdigit(ch)) {if (ch=='-') neg=;ch=getchar();}

    while (isdigit(ch)) re=re*+ch-'',ch=getchar();

    if (neg) re=-re; return re;

}

int n,m,U;

int p2[M],coe[<<N],g[N][N];

int f[<<N],deg[<<N],sum[<<N];

void readin(){

    n=read(),m=read();

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

        g[read()-][read()-]=;

    U=(<<n)-;

}

void prework(){

    p2[]=;coe[]=-;

    for (int i=;i<=m;i++){

        p2[i]=p2[i-]<<;

        if (p2[i]>=P) p2[i]%=P;

    }

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

        coe[i]=coe[i>>];

        if (i&) coe[i]*=-;

    }

}

void dp(){

    f[]=;

    for (int i=;i<U;i++){

        for (int j=;j<n;j++)deg[<<j]=;

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

            for (int k=;k<n;k++) deg[<<k]+=g[j][k];

        int C=U^i;sum[]=;

        for (int tmp=(C-)&C;;tmp=(tmp-)&C){

            int Now=C^tmp;

            sum[Now]=sum[Now-(Now&-Now)]+deg[Now&-Now];

            f[i^Now]=(f[i^Now]+(ll)f[i]*p2[sum[Now]]*coe[Now])%P;

            if (!tmp) break;

        }

    }

}

int main(){

    readin();

    prework();

    dp();

    printf("%d\n",f[U]);

    return ;

}

巴特西

【2016NOIP十连测】【test4】【状压DP】【容斥原理】巨神兵

最新文章

热门文章