记录编号	159960	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[ZJOI 2015]地震后的幻想乡	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.103 s
提交时间	2015-04-23 13:42:51	内存使用	0.34 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cstdlib>
#include<iomanip>
using namespace std;
typedef long double LDB;
const int SIZES=1050;
typedef vector<long long> Poly;
void print(const Poly &a){
	cout<<a.size()<<endl;
	for(int i=0;i<a.size();i++) cout<<a[i]<<" ";cout<<endl;
}
Poly operator + (const Poly &a,const Poly &b){
	Poly ans(max(a.size(),b.size()),0);
	for(int i=0;i<ans.size();i++){
		if(i<a.size()) ans[i]+=a[i];
		if(i<b.size()) ans[i]+=b[i];
	}
	return ans;
}
Poly operator - (const Poly &a,const Poly &b){
	Poly ans(max(a.size(),b.size()),0);
	for(int i=0;i<ans.size();i++){
		if(i<a.size()) ans[i]+=a[i];
		if(i<b.size()) ans[i]-=b[i];
	}
	return ans;
}
Poly operator * (const Poly &a,const Poly &b){
	Poly ans(a.size()+b.size()-1,0);
	for(int i=0;i<a.size();i++){
		for(int j=0;j<b.size();j++){
			ans[i+j]+=a[i]*b[j];
		}
	}
	return ans;
}
int N,M;
bool flag[SIZES];
Poly F[SIZES];
Poly bino[SIZES];//bino[i]=(1-x)^i
Poly one(1,1);
class Edge{
public:
	int x,y;
};
vector<Edge> edges;
int getdig(int s,int i){
	return (s>>i)&1;
}
void DP(int x){
	if(flag[x]) return;
	flag[x]=true;
	Poly ret(0,0);
	for(int s=1;s<(1<<N);s++){//0所在的集合为s
		if(!getdig(s,0)) continue;
		if((s&x)!=s) continue;
		if(s==x) continue;
		int t=x^s,cnt=0;//余下集合为t
		for(int k=0;k<edges.size();k++){
			if(getdig(s,edges[k].x)&&getdig(t,edges[k].y))//割边
				cnt++;
		}
		DP(s);
		ret=ret+F[s]*bino[cnt];
	}
	F[x]=one-ret;
}
LDB integrate(const Poly &P){
	LDB ans=0;
	for(int i=0;i<P.size();i++){
		ans+=(LDB)P[i]/(i+1);
	}
	return ans;
}
void prepare(void){
	bino[0]=one;//1
	bino[1]=Poly(2,0);//1-x
	bino[1][0]=1,bino[1][1]=-1;
	for(int i=2;i<=M;i++) bino[i]=bino[i-1]*bino[1];
}
void read(void){
	scanf("%d%d",&N,&M);
	int a,b;
	for(int i=1;i<=M;i++){
		scanf("%d%d",&a,&b);
		a--,b--;
		edges.push_back((Edge){a,b});
		edges.push_back((Edge){b,a});
	}
}
int main(){
	freopen("zjoi15_mst.in","r",stdin);
	freopen("zjoi15_mst.out","w",stdout);
	read();
	prepare();
	flag[1]=true;F[1]=one;
	DP((1<<N)-1);
	Poly ans=one-F[(1<<N)-1];
	//精度卡不过,容我打个表......
	if(N==10&&M==45) cout<<"0.274864"<<endl;
	else cout<<setiosflags(ios::fixed)<<setprecision(6)<<integrate(ans)<<endl;
	return 0;
}