描述
某天，高富帅clj送了他的朋友jzp一个小玩具。
这个玩具可以被看成是一个n个点，m条边的没有重边和自环的无向图。对于每一条边，有闪光和黑暗两种状态。
jzp可以把一些边设为闪光，一些边设为黑暗。当jzp设置完成以后，这个玩具会按照如下方式计算出一个分数。首先称闪光边和这n个点组成的图为导出子图，然后玩具会找出导出子图中最大的联通分量的大小，当做分数输出。
jzp有一天很闲，他尝试了所有的2m种边的设置方式（每个边为闪光或者黑暗），并且计算出了每种分数的出现次数。写在了一张纸上。
但是很不走运的是，这张纸某一天被他给搞丢了。现在我告诉你这个图，你能帮助他重新计算出每种分数的出现次数吗？
输入
第一行两个数n(1<=n<=15)和m(0<=m<=n(n-1)/2)，分别表示玩具中图的点数和边数。接下来m行，每行两个数a和b，表示a和b之间有一条边。
点从1开始标号。
输出
一共输出n行，第i行表示分数i的出现次数，对10^9+7取模。
样例输入
3 3 1 2 1 3 2 3
样例输出
1 3 4
妈妈做WJMZBER的题鸭梨山大。
首先转化问题，设ans[k]表示所有连通分量大小均<=k的方案。
则最大连通分量为k的方案转化成ans[k]-ans[k-1]
然后就可以DP了，考虑从一个集合S中慢慢剥离连通分量。设f[S]表示将集合S中的点分配且满足要求的方案。
枚举S的最低位的元素x所在的集合S0，则f[S]=(|S|<=k?g[S]:0)+∑(f[S0]*g[S0]|S0⊂S,|S0|<=k,{x}⊂S)
其中g[S]表示S中的点均连通的方案数。
计算g[S]是我们可以用容斥原理，将S中的点均连通的方案数转化成全集-S中的点不连通的方案数。计算时依然枚举S的最低位的元素x所在的集合S0，算算就行了。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=16; const int mod=1000000007; typedef long long ll; int n,m,es[1<<maxn],u[maxn*maxn],v[maxn*maxn],cnt[1<<maxn]; ll g[1<<maxn],f[1<<maxn],xp[maxn*maxn],ans[maxn]; int main() { n=read();m=read(); rep(i,1,m) u[i]=read()-1,v[i]=read()-1; rep(S,0,(1<<n)-1) { rep(i,0,n-1) if(S&(1<<i)) cnt[S]++; rep(i,1,m) if((S&(1<<u[i]))&&(S&(1<<v[i]))) es[S]++; } xp[0]=1; rep(i,1,m) xp[i]=(xp[i-1]<<1)%mod; g[0]=1; rep(S,1,(1<<n)-1) { int bit=S&-S; for(int S0=(S-1)&S;S0;S0=(S0-1)&S) if(bit&S0) { (g[S]+=g[S0]*xp[es[S^S0]])%=mod; } g[S]=(xp[es[S]]-g[S]+mod)%mod; } rep(T,1,n) { f[0]=1; rep(S,1,(1<<n)-1) { f[S]=cnt[S]<=T?g[S]:0;int bit=S&-S; for(int S0=(S-1)&S;S0;S0=(S0-1)&S) if((bit&S0)&&cnt[S0]<=T) (f[S]+=f[S0^S]*g[S0])%=mod; } ans[T]=f[(1<<n)-1]; if(T) printf("%lld ",(ans[T]-ans[T-1]+mod)%mod); } return 0; }