【原题题面】传送门
【题解大意】
如果将状态设置为f[i]表示从1到i的路径xor期望值，很明显是不可转移的。
为了满足期望的线性，我们考虑二进制下一位一位地做。
f[i]表示在当前位下的期望值。
如果边权在当前为下为1，f[i] += （1-f[j]）/deg[i];
（如不理解可以手动模拟一下f[j]==0和f[j]==1当边权为1时对答案的贡献。
对于我们要高斯消元的矩阵来说,
a[i][j] += 1/deg[i],a[i][0] += 1.deg[i];
否则，a[i][j] -= 1/deg[i];
再然后进行消元就好了。
【code】
#include<bits/stdc++.h> using namespace std; #define File "" #define ll long long inline void file(){ freopen(File".in","r",stdin); freopen(File".out","w",stdout); } inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*f; } const int mxm = 1e4+5; const int mxn = 1e2+3; int n,m; struct edge{ int nxt,y,v; }e[mxm<<1]; int to[mxm],len; inline void add(int xx,int yy,int vv){ e[++len].nxt = to[xx]; to[xx] = len; e[len].y = yy; e[len].v = vv; } int deg[mxn]; double ans,a[mxn][mxn],b[mxn]; inline void wor(){ for(int i = 1;i < n; ++i){ int now = i; for(int j = i+1;j < n; ++j) if(fabs(a[j][i]) > fabs(a[now][i])) now = j; for(int j = 0;j <= n; ++j) swap(a[i][j],a[now][j]); for(int j = i+1;j <= n; ++j){ double w = a[j][i] / a[i][i]; for(int k = 0;k <= n; ++k) a[j][k] = a[i][k]*w - a[j][k]; } } //每行只有一个数不为零，每列只有一个数不为零的矩阵 for(int i = n; i; --i){ for(int j = i+1; j <= n; ++j) a[i][0] -= a[i][j] * b[j]; b[i] = a[i][0] / a[i][i]; //对应的数字除去该行的非零系数，即为对应该元的解 } } int main(){ // file(); n = read(),m = read(); for(int i = 1;i <= m; ++i){ int x = read(),y = read(),z = read(); add(x,y,z),deg[x]++; if(x!=y) add(y,x,z),deg[y]++; } for(int i = 0;i < 31; ++i){ //赋初值 memset(a,0,sizeof a); memset(b,0,sizeof b); for(int x = 1;x <= n; ++x) a[x][x] = 1; for(int x = 1;x < n; ++x){ for(int j = to[x]; j;j = e[j].nxt){ int y = e[j].y,z = e[j].v; if((z>>i)&1) a[x][y] += 1.0/deg[x], a[x][0] += 1.0/deg[x]; else a[x][y] -= 1.0/deg[x]; } } wor(); ans += b[1] * (1<<i); } printf("%.3f ",ans); return 0; } /* 2 2 1 1 2 1 2 3 */