https://www.luogu.com.cn/problem/P3211
用到在 dp 的转移中出现环时，把按顺序转移改为解方程的思路
整体计算比较困难，考虑把每一位拆开来算
对于当前位，设 (f_u) 表示从 (u) 到 (n)，当前位为 (1) 的概率；设 (deg_u) 为 (u) 的度数，并令 (w(u,v)) 表示边权上当前这一位是 (0/1)
那么根据异或的性质，就可以得出转移方程：
[f_u=frac{1}{deg_u}left(sum_{w(u,v)=0}f_v+sum_{w(u,v)=1}(1-f_v)
ight)
]
但发现这是一个一般的图，转移过程中会出现环，那么就可以把他化成方程的形式，用解方程的方法来处理
[deg_ucdot f_u+sum_{w(u,v)=1}f_v-sum_{w(u,v)=0}f_v=sum_{w(u,v)=1} 1
]
这样对于每一个 (1le u le n-1) 都可以写出这样一个方程，对于第 (n) 个方程，由于 (f_n=0)，所以直接令 (b_n=0,a_{nn}=1)，即可
最后高斯消元就行了
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define reg register
#define LL_INF (long long)(0x3f3f3f3f3f3f3f3f)
#define INT_INF (int)(0x3f3f3f3f)
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=getchar();}
return y?x:-x;
}
#define N 106
#define M 20006
struct Graph{
int fir[N],nex[M],to[M],w[M],tot;
inline void add(reg int u,int v,int z){
to[++tot]=v;w[tot]=z;
nex[tot]=fir[u];fir[u]=tot;
}
}G;
int n,m;
int deg[N],a[N][N];
double b[N],z[N],f[N];
double u[N][N],l[N][N];
inline void lu_div(){
for(reg int i=1;i<=n;i++){
for(reg int j=i;j<=n;j++){
u[i][j]=a[i][j];
for(reg int k=1;k<i;k++) u[i][j]-=l[i][k]*u[k][j];
l[j][i]=a[j][i];
for(reg int k=1;k<i;k++) l[j][i]-=l[j][k]*u[k][i];
l[j][i]/=u[i][i];
}
l[i][i]=1;
}
}
inline void solve_z(){
for(reg int i=1;i<=n;i++){
z[i]=b[i];
for(reg int j=1;j<i;j++) z[i]-=z[j]*l[i][j];
}
}
inline void solve_f(){
for(reg int i=n;i;i--){
f[i]=z[i];
for(reg int j=n;j>i;j--) f[i]-=f[j]*u[i][j];
f[i]/=u[i][i];
}
}
inline void solve(){lu_div();solve_z();solve_f();}
inline void build(int base){
for(reg int u=1;u<n;u++){
for(reg int j=1;j<=n;j++) a[u][j]=0;
b[u]=0;
a[u][u]=deg[u];
for(reg int v,i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(G.w[i]&base) a[u][v]++,b[u]++;
else a[u][v]--;
}
}
b[n]=0;a[n][n]=1;
}
int main(){
// std::freopen("out.txt","w",stdout);
n=read();m=read();
for(reg int u,v,w,i=1;i<=m;i++){
u=read();v=read();w=read();
G.add(u,v,w);deg[u]++;
if(u^v) G.add(v,u,w),deg[v]++;
}
double ans=0;
for(reg int i=0;i<=30;i++){
build(1<<i);solve();
ans+=f[1]*(1<<i);
// for(reg int i=1;i<=n;i++){
// for(reg int j=1;j<=n;j++) printf("%d ",a[i][j]);
// puts("");
// }
}
printf("%.3lf
",ans);
return 0;
}