http://www.lydsy.com/JudgeOnline/problem.php?id=2337
概率不能异或
但根据期望的线性，可以计算出每一位为1的概率，再累积他们的期望
枚举每一位i，现在要计算从1出发第i位异或和为1的概率
令f[u]表示从点u出发，第i为为1的概率
d[u]表示u的度数
枚举与u相连的v
若边权的第i位为1，那么v的第i位为0，f[u]+=(1-f[v])/d[u]
若边权的第i位为0，那么v的第i位为1，f[u]+=f[v]/d[u]
还有一个f[n]=0
将这n个式子，f[i]看做未知数，1/d[i]看做系数
把f[i]都移到左边，1/d 都移到右边
得到n个方程，高斯消元解出来
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> using namespace std; #define N 101
#define M 10001 const double eps=1e-; int n; int d[N];
int to[M<<],nxt[M<<],front[N],val[M<<],tot; double a[N][N]; int bit[]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int u,int v,int w)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w;
} void gauss()
{
int r;
double f;
for(int i=;i<n;++i)
{
r=i;
for(int j=i+;j<n;++j)
if(abs(a[j][i])>abs(a[r][i])) r=j;
if(r!=i) swap(a[r],a[i]);
for(int k=i+;k<n;++k)
{
f=a[k][i]/a[i][i];
for(int j=i;j<=n;++j) a[k][j]-=f*a[i][j];
}
}
for(int i=n-;i>=;--i)
{
for(int j=i+;j<n;++j) a[i][n]-=a[j][n]*a[i][j];
a[i][n]/=a[i][i];
}
} int main()
{
int m;
read(n); read(m);
int x,y,w;
while(m--)
{
read(x); read(y); read(w);
add(x,y,w),d[y]++;
if(x!=y) add(y,x,w),d[x]++;
}
bit[]=;
for(int i=;i<;++i) bit[i]=bit[i-]<<;
double ans=;
for(int i=;i<;++i)
{
memset(a,,sizeof(a));
for(int j=;j<n;++j)
{
a[j-][j-]=;
for(int k=front[j];k;k=nxt[k])
if(val[k]&bit[i])
{
a[j-][to[k]-]+=1.0/d[j];
a[j-][n]+=1.0/d[j];
}
else a[j-][to[k]-]-=1.0/d[j];
}
a[n-][n-]=;
gauss();
ans+=a[][n]*bit[i];
}
printf("%.3lf",ans);
}