【 HDU 4936 】Rainbow Island （hash + 高斯消元）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#define N 22
#define M 1000007
using namespace std;
int cas,t,n,cnt,a[N];
int f[M+1],mg[700][N][N];
//f[code]：code对应的状态
//mg[s][x][y]:状态s的第x和第y个合并后的状态
double p[N],dp[700][N],g[N][N];
//dp[st][i]，当前状态st，人在第i个岛上，到达目标状态的期望值
vector<int>s[N];

struct sta{
	int a[N],tot;
}st[700];

int code(sta t){
	int b=t.tot;
	for(int i=1;i<=t.tot;i++)
		b=(b*233%M+t.a[i])%M; //hash
	return b;
}
void dfs(int d,int k,int sum){
	if(sum==n){
		sta &t=st[++cnt];
		t.tot=d-1;
		for(int i=1;i<d;i++)
			t.a[i]=a[i];
		f[code(t)]=cnt;
		return;
	}
	for(int i=k;i<=n-sum;i++)
		dfs(d+1,a[d]=i,sum+i);
}
int merge(sta t,int x,int y){
	t.a[x]+=t.a[y];
	swap(t.a[y],t.a[t.tot--]);
	sort(t.a+1,t.a+t.tot+1);
	return f[code(t)];
}

void pre(){
//求出所有可能的状态并hash处理，求出合并两个联通块后对应的状态
	cnt=0;
	dfs(1,1,0);
	for(int i=1;i<=cnt;i++)
		for(int x=1;x<st[i].tot;x++)
		for(int y=x+1;y<=st[i].tot;y++)
			mg[i][x][y]=merge(st[i],x,y);
}
void gauss(double x[]){
	for(int i=1;i<=n;i++){
		int r=i;
		while(!g[r][i]&&r<=n)r++;
		if(r>n)return;
		swap(g[r],g[i]);
		for(int j=i+1;j<=n;j++){
			double t=g[j][i]/g[r][i];
			for(int k=1;k<=n+1;k++)
				g[j][k]-=t*g[r][k];
		}
	}
	for(int i=n;i;i--)if(g[i][i]){//注意判断
		x[i]=g[i][n+1]/g[i][i];
		for(int j=1;j<i;j++)
			g[j][n+1]-=g[j][i]*x[i];
	}
}
void work(){
	memset(dp,0,sizeof dp);
	for(int i=cnt-1;i>=1;i--){
		memset(g,0,sizeof g);
		for(int j=1;j<=n;j++){
			double b=1;
			for(int x=1;x<st[i].tot;x++)
			for(int y=x+1;y<=st[i].tot;y++){
				int k=mg[i][x][y];
				double ps=p[j]*st[i].a[x]*st[i].a[y]/(n*(n-1)/2)/s[j].size();
				for(int u=0;u<s[j].size();u++){
					int v=s[j][u];
					b+=dp[k][v]*ps;
				}
			}
			g[j][j]=1;
			g[j][n+1]=b;
			double ps=0;
			for(int x=1;x<=st[i].tot;x++)
				ps+=st[i].a[x]*(st[i].a[x]-1);//连接同一联通块的岛的彩虹个数*2
			ps/=n*(n-1);//除以 2*总的彩虹个数(n*(n-1)/2)
			ps=(ps*p[j]+1-p[j])/s[j].size();
			for(int u=0;u<s[j].size();u++){
				int v=s[j][u];
				g[j][v]-=ps;
			}
		}
		gauss(dp[i]);
	}
}
int main() {
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%lf",&p[i]),s[i].clear();
		for(int i=1,t,v;i<=n;i++){
			scanf("%d",&t);
			while(t--){
				scanf("%d",&v);
				s[i].push_back(v);
			}
		}
		pre();
		work();
		printf("Case #%d: %f\n",++cas,dp[1][1]);
	}	
	return 0;
}