有人说这题像游走...
关于游走的思想，他死了...
明明直接从期望dp的角度考虑更简单合理嘛
首先由于是异或运算不妨逐位考虑
对于每一位，设状态$f[i]$表示从第$i$个点到第$n$个点，这一位上是$1$的概率
那么我们按边权讨论转移：
若这条边边权为$1$：$f[i]+=frac{1-f[to]}{deg_{i}}$
若这条边边权为$0$：$f[i]+=frac{f[to]}{deg_{i}}$
可是本题转移是成环的，因此直接dp是行不通的
但是我们可以考虑高斯消元嘛！
上面那个表达式很显然是个方程组，高斯消元解之即可！
整理一下，就得到了：$deg_{i}f[i]+[v_{i,to}==1]f[to]-[v_{i,to}==0]f[to]=sum_{v_{i,to}==1}1$
（其实就是整合一下上面两个表达式，移个项就出来了）
算出$f[1]$乘贡献即可
（所以这题根本不需要基于点考虑边，只需要考虑点就可以了！不用研究边的期望！）
贴代码：
#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <vector> using namespace std; double eps=1e-8; struct Edge { int nxt; int to; int val; }edge[20005]; int head[105]; double inr[105]; double a[105][105]; int n,m,cnt=1; double ans=0; void add(int l,int r,int w) { edge[cnt].nxt=head[l]; edge[cnt].to=r; edge[cnt].val=w; head[l]=cnt++; inr[l]++; } void Gauss() { for(int i=1;i<=n;i++) { int temp=i; while(fabs(a[temp][i])<=eps)temp++; if(temp!=i)for(int j=i;j<=n;j++)swap(a[i][j],a[temp][j]); double now=a[i][i]; for(int j=i;j<=n+1;j++)a[i][j]/=now; for(int j=i+1;j<=n;j++) { if(fabs(a[j][i])<=eps)continue; now=a[j][i]; for(int k=i;k<=n+1;k++)a[j][k]-=now*a[i][k]; } } for(int i=n;i>=1;i--)for(int j=i-1;j>=1;j--)a[j][n+1]-=a[i][n+1]*a[j][i]; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); if(x!=y)add(y,x,z); } for(int k=0;k<=30;k++) { memset(a,0,sizeof(a)); for(int i=1;i<=n-1;i++) { a[i][i]=inr[i]; for(int j=head[i];j;j=edge[j].nxt) { int to=edge[j].to; if(edge[j].val&(1<<k))a[i][to]+=1.0,a[i][n+1]+=1.0; else a[i][to]-=1.0; } } a[n][n]=1; Gauss(); ans+=a[1][n+1]*(1<<k); } printf("%.3lf ",ans); return 0; }