Description
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
期望+高斯消元~
先在加边的时候预处理出每个点的出边数siz,然后分位数期望,枚举当前是第几位,然后设a[i][j]表示从i到j,并且该位是一的期望概率,那么如果改变权值val&(1<<k)(k为目前位),那么a[i][j]+=1/siz[i],否则减去。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;int n,m,x,y,z,fi[102],w[20001],ne[20001],v[20001],cnt,siz[102];
double a[102][102],ans;int read()
{int totnum=0,f=1;char s=getchar();while(s<'0' || s>'9') {if(s=='-') f=-1;s=getchar();}while(s>='0' && s<='9') {totnum=totnum*10+s-'0';s=getchar();}return totnum*f;
}void add(int u,int vv,int val)
{w[++cnt]=vv;ne[cnt]=fi[u];fi[u]=cnt;v[cnt]=val;siz[u]++;
}void cal()
{for(int i=1;i<=n;i++){int now=i;double maxx=0;for(int j=i;j<=n;j++)if(fabs(a[j][i])>maxx) maxx=fabs(a[j][i]),now=j;if(now!=i) for(int j=1;j<=n+1;j++) swap(a[now][j],a[i][j]);double kkz=a[i][i];for(int j=1;j<=n+1;j++) a[i][j]/=kkz;for(int j=1;j<=n;j++)if(i!=j){double kkz=a[j][i];for(int k=1;k<=n+1;k++) a[j][k]-=kkz*a[i][k];}}
}int main()
{n=read();m=read();for(int i=1;i<=m;i++){x=read(),y=read(),z=read(),add(x,y,z);if(x!=y) add(y,x,z);}for(int i=0;i<=30;i++){memset(a,0,sizeof(a));for(int j=1;j<n;j++){a[j][j]=1;for(int k=fi[j];k;k=ne[k])if(v[k]&(1<<i)) a[j][w[k]]+=(double)1/siz[j],a[j][n+1]+=(double)1/siz[j];else a[j][w[k]]-=(double)1/siz[j];}a[n][n]=1;cal();ans+=(double)a[1][n+1]*(1<<i);}printf("%.3lf\n",ans);return 0;
}