牛客挑战赛53 C.奇奇怪怪的魔法阵(状压)

Link

我们要求$f_T=\sum _{S\in T}[S\mathrm{为}\mathrm{独}\mathrm{立}\mathrm{集}]f\_T=\backslash sum\backslash limits\_\{S\backslash in\; T\}[S为独立集]$

考虑集合$TT$的最低位二进制位代表的集合是$yy$(这个点设为$uu$),其他二进制位代表的是$xx$

那么$T=x+yT=x+y$

显然,若$SS$集合中不包含集合$yy$(点$uu$),方案数为$f_{x}f\_x$

$SS$集合中不包含集合$xx$,方案数为$f_y=1f\_y=1$

若$SS$中包含集合$yy$且包含集合$xx$中的部分点

需要满足包含的集合$xx$中那些点不与点$uu$有边

这个简单,我们令二进制数$va{l}_{u}val\_u$表示哪些点与$uu$有边

那么集合$xx$中满足条件的点就是

总转移为

$f_T=f_x+f_y+f_{x\oplus va{l}_u}f\_T=f\_x+f\_y+f\_\{x\backslash oplus\; val\_u\}$

总体复杂度为$O(2^n)O(2^n)$

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1<<26;
const int mod = 1e9+7;
int n,m,f[maxn],k[maxn],val[28];
int lowbit(int x){ return x&(-x); }
int main()
{
	cin >> n >> m;
	for(int i=0;i<n;i++)	k[1<<i] = i;
	for(int i=1;i<=m;i++)
	{
		int l,r; cin >> l >> r;
		val[l] |= (1<<r); val[r] |= (1<<l);
	}
	for(int i=1;i<(1<<n);i++)
	{
		int y = lowbit( i ), x = i-y, z = x^( x&val[k[y]] );
		if( i==y )	f[i] = 1;
		else	f[i] = ( 1ll*f[z]+f[y]+f[x] )%mod;
	}
	long long ans = 0, res = 1;
	for(int i=0;i<(1<<n);i++)
	{
		ans = ( ans+1ll*res*( f[i]+1 )%mod )%mod;
        res = 1ll*res*233%mod;
	}
	cout << ans;
}