BZOJ3812 主旋律（状压dp+容斥原理）

时间：2022-07-24 04:21:35

　　设f[S]为S点集是SCC的方案数。考虑通过去掉不合法方案转移。可以枚举入度为0的SCC所含点集S'，这样显然S^S'内部的边和由S'连向S^S'的边删还是不删任选。但是这样无法保证S'包含所有入度为0的SCC，于是考虑容斥，瞎猜可以得到容斥系数与SCC数量有关，于是设g[i][S]为S包含i个无关SCC的方案数，转移有f[S]=2cnt(S)-Σ(-1)j*g[j][S']*2cnt(S^S')+cnt(S' to S^S')，g的转移通过枚举编号最小点所在SCC实现。注意到g[j][]的贡献只与j的奇偶性有关，于是可以改成g[S]为S有偶数个无关SCC的方案数，h[S]为S有奇数个无关SCC的方案数，转移类似。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 15

#define P 1000000007

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,m,a[N][N],e[1<<N],s[N][1<<N],p[N*N*N],f[1<<N],g[1<<N],h[1<<N];

int trans(int x)

{

	int s=-1;

	while (x) s++,x>>=1;

	return s;

}

int calc(int x,int y)

{

	int u=0;

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

	if (x&(1<<i)) u+=s[i][y];

	return u;

}

int main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

	const char LL[]="%I64d\n";

#else

	const char LL[]="%lld\n";

#endif

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

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

	{

		int x=read()-1,y=read()-1;

		a[x][y]=1;

	}

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

		for (int x=0;x<n;x++)

		if (i&(1<<x))

			for (int y=0;y<n;y++)

			if (i&(1<<y)) e[i]+=a[x][y];

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

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

		s[i][j]=s[i][j^(j&-j)]+a[i][trans(j&-j)];

	p[0]=1;for (int i=1;i<=m;i++) p[i]=(p[i-1]<<1)%P;

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

	{

		f[i]=p[e[i]];

		int x=0;

		for (int j=0;j<n;j++) if (i&(1<<j)) {x=j;break;}

		for (int j=i-1&i;j;j=j-1&i)

		if (j&(1<<x))

		{

			g[i]=(g[i]+1ll*h[i^j]*f[j])%P;

			h[i]=(h[i]+1ll*g[i^j]*f[j])%P;

		}

		for (int j=i;j;j=j-1&i)

		f[i]=(f[i]+1ll*(g[j]+P-h[j])*p[e[i^j]+calc(j,i^j)]%P)%P;

		h[i]=(h[i]+f[i])%P;

	}

	cout<<f[(1<<n)-1];

	return 0;

}

　　

相关文章