Solution
我们可以发现这个题和游走很像（虽然游走是HNOI2013，这个是HNOI2011吧）
但是这个题是要求异或和，每一位是互不干扰的，再加上期望的线性性，所以考虑每一位单独计算。
我们设 (f_i) 表示从 (i) 到 (n) 路径这一位异或和为 (1) 的概率，那么我们可以显然的得到转移方程：
[f_u=sum_{vin w_{u,v} 此位为 0} frac {f_v}{d_u}+sum_{vin w_{u,v} 此位为 1} frac {1-f_v}{d_u}
]
（其中 (w_{u,v}) 表示 (langle u,v angle) 这条边的边权， (d_u) 表示 (u) 的度数，即与 (u) 相连的边数，包括自环）
前面的 (sum) 表示要在 (v) 中找 (0) 的概率，后面的表示要在 (v) 中找 (1) 的概率。
我们发现这个方程是有后效性的，所以还要继续考虑。发现进一步转化可以得到：
[-sum_{vin w_{u,v} 此位为 1}frac 1{d_u}=-f_u+sum_{vin w_{u,v} 此位为 0} frac {f_v}{d_u}-sum_{vin w_{u,v} 此位为 1} frac {f_v}{d_u}
]
哦~这长得很像 (n-1) 元方程啊，而我们总共有 (n-1) 个方程，所以考虑用高斯消元求解。
（ 因为到达 (n) 的时候就停止了，所以 (f_n=0) ，在计算的时候不考虑）
再简单的提一下计算答案： 设当前位为 (i) ，那就 (ans+=f_1 imes 2^i) 即可。
注意：一个自环只能增加一条边，重边在累加方程系数的时候都要算上。
时间复杂度为 (O(n^3log w))
完结撒花
你不会以为这就完了吧(⊙_⊙)
为什么是从 (u) 到 (n) 逆推呢？我相信只有我一个蒟蒻感到疑惑，但是还是要说一下。
因为异或和不为 (1) 的概率是 (1-f_u) ，但是正推此时的含义是： (1) 到 (u) 异或和不为 (1) 的概率和从 (1) 无法走到 (u) 的概率；但是逆推的话， (1-f_u) 就还是走到 (n) ヾ(≧▽≦*)o
正式完结撒发。
Code
#include<bits/stdc++.h>
#define re register
using namespace std;
const int N=110;
const double eps=1e-9;
int n,m,head[N],cnt,d[N],pw[N];
double a[N][N],f[N],ans;
struct edge{
int to,nxt,w;
}e[N*N<<1];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
return x*f;
}
inline void add(int u,int v,int w){
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
d[v]++;
}
inline void Gauss(){
for(re int i=1;i<n;i++)
for(re int j=i+1;j<=n;j++){
double tmp=a[j][i]/a[i][i];
for(re int k=1;k<=n+1;k++) a[j][k]-=a[i][k]*tmp;
}
for(re int i=n;i;i--){
f[i]=a[i][n+1]/a[i][i];
for(re int j=i-1;j;j--) a[j][n+1]-=a[j][i]*f[i];
}
}
int main(){
n=read(); m=read();
memset(head,-1,sizeof(head));
pw[0]=1;
for(re int i=1;i<=30;i++) pw[i]=pw[i-1]*2;
for(re int i=1,u,v,w;i<=m;i++){
u=read(); v=read(); w=read();
add(u,v,w); if(u!=v) add(v,u,w);
}
for(re int i=0;i<=30;i++){
memset(a,0,sizeof(a)); a[n][n]-=1.0;
for(re int u=1;u<n;u++){
a[u][u]=-1;
for(re int j=head[u];j!=-1;j=e[j].nxt){
int v=e[j].to;
if(~e[j].w&pw[i]) a[u][v]+=1.0/d[u];
else a[u][n+1]-=1.0/d[u],a[u][v]-=1.0/d[u];
}
}
Gauss();
ans+=f[1]*pw[i];
}
printf("%.3lf
",ans);
return 0;
}
小彩蛋：题目描述中的第一段的题也是真实出现的，就是介个。