【 HDU 4936 】Rainbow Island （hash + 高斯消元）---饶文津

BUPT2017 wintertraining(15) #5B HDU - 4936 2014 Multi-University Training Contest 7 F

题意

直接看官方的题意和题解吧（来自：2014年多校的题解博客）。

题解

官方的不够细，我再梳理一下吧。

预处理：

高斯消元

代码#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: %fn",++cas,dp[1][1]); } return 0; } ---来自腾讯云社区的---饶文津