题面链接

洛咕

sol

%%%_rqy

本来想写正常的状压，看到这篇题解就入坑了。。。

直接搬题解吧，写的太好了不用解释。

慢慢搬，先咕着QAQ

#include<cstdio>

#include<cstring>

#include<algorithm>

#define gt getchar()

#define ll long long

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

inline int in()

{

	int k=0;char ch=gt;

	while(ch<'-')ch=gt;

	while(ch>'-')k=k*10+ch-'0',ch=gt;

	return k;

}

int cnt[1<<11],du[11];

double dp[1<<11][55];

int main()

{

	int n=in(),m=in();

	int S=1<<n;

	for(int i=1;i<S;++i)cnt[i]=cnt[i>>1]+(i&1);

	for(int i=1;i<=m;++i)

	{

		int x=in(),y=in();

		du[x]|=(1<<y-1);

		du[y]|=(1<<x-1);

	}

	for(int S1=3;S1<S;++S1)

		if(S1&1)

			for(int S2=(S1-1)&S1;S2;S2=(S2-1)&S1)

				if(S2&1)

				{

					int res=0;

					for(int i=0;i<n;++i)

						if((S1>>i)&(~S2>>i)&1)

							res+=cnt[du[i+1]&S2];

					for(int i=0;i+res<=m;++i)

						dp[S1][i]+=1.0/(i+res+1)-dp[S2][i+res];

				}

	printf("%.6lf\n",dp[S-1][0]);

	return 0;

}