P3343 [ZJOI2015]地震后的幻想乡

传送门

给积分大佬跪了

再给状压大佬也跪了

//minamoto

#include<bits/stdc++.h>

#define rint register int

#define ll long long

using namespace std;

#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

char buf[1<<21],*p1=buf,*p2=buf;

int read(){

    int res,f=1;char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

ll dp[2][65][2205],sz[2205];bool vis[2205];

int n,m,up,mp[25][25];ll c[60][60];double res;

int main(){

//	freopen("testdata.in","r",stdin);

	n=read(),m=read(),up=pow(2,n)-1;

	for(rint i=1,u,v;i<=m;++i)u=read(),v=read(),mp[u-1][v-1]=mp[v-1][u-1]=1;

	for(rint i=1;i<=up;++i)for(rint p1=1;p1<n;++p1)for(rint p2=0;p2<p1;++p2)sz[i]+=((i>>p1)&1)&&((i>>p2)&1)&&mp[p1][p2];

//	for(rint i=0;i<=m+1;++i)c[i][0]=c[i][i]=1;

//	for(rint i=1;i<=m+1;++i)for(rint j=1;j<i;++j)c[i][j]=c[i-1][j]+c[i-1][j-1];

	for(rint i=0;i<=m+1;++i)c[0][i]=c[i][i]=1;

	for(rint j=1;j<=m+1;++j)for(rint i=1;i<j;++i)c[i][j]=c[i][j-1]+c[i-1][j-1];

	for(rint i=0;i<=up;++i)dp[0][0][i]=1;

	for(rint i=0;i<n;++i)dp[1][0][1<<i]=1,dp[0][0][1<<i]=0;

	for(rint i=1;i<=m;++i)for(rint j=1;j<=up;++j){

		int p1=0;while(((j>>p1)&1)==0)++p1;

		for(rint k=(j-1)&j;k;k=(k-1)&j){

			if(((k>>p1)&1)==0)continue;

			for(rint rk=0;rk<=i;++rk)

			dp[0][i][j]+=dp[1][rk][k]*c[i-rk][sz[j^k]];

		}

		dp[1][i][j]=c[i][sz[j]]-dp[0][i][j];

	}

	for(rint i=0;i<=m;++i)res+=1.0*dp[0][i][up]/c[i][m];

	printf("%.6lf\n",res/(m+1));return 0;

}