【题意】给定n个点m条边的带边权无向连通图（有重边和自环），在每个点随机向周围走一步，求1到n的期望路径异或值。n<=100，wi<=10^9。
【算法】期望+高斯消元
【题解】首先异或不满足期望的线性，所以考虑拆位。
对于每一个二进制位，经过边权为0仍是x，经过边权为1变成1-x（转化成减法才满足期望的线性）。
设f[x]表示点x到n的路径xor期望，f[n]=0，根据全期望公式：
$$f[i]=\sum_{j}\frac{f[j]}{out[i]}\ \ , \ \ w(i,j)=0$$
$$f[i]=\sum_{j}\frac{1-f[j]}{out[i]}\ \ , \ \ w(i,j)=1$$
因为有循环所以用高斯消元求解，复杂度O(n^3*log wi)。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=;
struct edge{int v,w,from;}e[maxn*maxn*];
int n,m,first[maxn],tot,out[maxn];
long double a[maxn][maxn],ans;
void insert(int u,int v,int w){tot++;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;out[u]++;}
void gauss(){
for(int i=;i<n;i++){
int r=i;
for(int j=i+;j<=n;j++)if(fabs(a[j][i])>fabs(a[r][i]))r=j;
if(r!=i)for(int j=i;j<=n+;j++)swap(a[i][j],a[r][j]);
for(int j=i+;j<=n;j++)
for(int k=n+;k>=i;k--)
a[j][k]-=a[j][i]/a[i][i]*a[i][k];
}
for(int i=n;i>=;i--){
for(int j=i+;j<=n;j++)a[i][n+]-=a[i][j]*a[j][n+];
a[i][n+]/=a[i][i];
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
insert(u,v,w);
if(u!=v)insert(v,u,w);//
}
for(int k=;k<=;k++){
memset(a,,sizeof(a));//
for(int x=;x<n;x++){
for(int i=first[x];i;i=e[i].from){
if(e[i].w&(<<k)){
a[x][e[i].v]--;//
a[x][n+]--;
}
else a[x][e[i].v]++;
}
a[x][x]-=out[x];//
}
a[n][n]=;
gauss();
ans+=a[][n+]*(<<k);
}
printf("%.3Lf",ans);
return ;
}
注意：
1.方程组右边是常数项。
2.自环不要重复加边。