【原题题面】

【题解大意】

如果将状态设置为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
      
       using namespace std;#define File ""#define ll long longinline 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<