程序员人生 网站导航

【BZOJ2560】串珠子

栏目:php教程时间:2015-03-11 08:02:32

广告:

#include <stdio.h> int main() { puts("转载请注明出处[vmurder]谢谢"); puts("网址:blog.csdn.net/vmurder/article/details/44060425"); }

题解:

gi 表示状态为i时随意连边时的方案个数
fi 表示状态为i时图是连通图的方案个数

gi好求,直接枚举1个里面的点a,然后向外面某点b连边得到 gi|(1<<b)
然后我们可以在从gi中减去某些东西得到fi
先肯定1个小的连通块,状态为a,然后其它点的状态就是i^a
然后明显ga×fi xor a就是要减去的。
肯定1个点x,然后以此为基础枚举连通块就行了。

代码:

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MOD 1000000007 #define N 20 #define M 101000 using namespace std; int n,S,a[N][N]; long long f[M],g[M]; int main() { int i,j,k,now; scanf("%d",&n); for(i=0;i<n;i++)for(j=0;j<n;j++)scanf("%d",&a[i][j]); S=1<<n; for(i=1;i<S;i++) { g[i]=1; for(j=0;j<n;j++)if(i&(1<<j)) for(k=j+1;k<n;k++)if(i&(1<<k)) g[i]=g[i]*(a[j][k]+1)%MOD; f[i]=g[i]; for(j=n-1;j+1;j--) if(i&(1<<j)){now=j;break;} now=i^(1<<now); for(j=now;j;j=(j-1)&now) // 枚举子集 f[i]=(f[i]-g[j]*f[i^j]%MOD+MOD)%MOD; } cout<<f[S-1]; }

Qwq

今天下午怎样突然好困。

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐