概率不能异或

但根据期望的线性，可以计算出每一位为1的概率，再累积他们的期望

枚举每一位i，现在要计算从1出发第i位异或和为1的概率

令f[u]表示从点u出发，第i为为1的概率

d[u]表示u的度数

枚举与u相连的v

若边权的第i位为1，那么v的第i位为0，f[u]+=(1-f[v])/d[u]

若边权的第i位为0，那么v的第i位为1，f[u]+=f[v]/d[u]

还有一个f[n]=0

将这n个式子，f[i]看做未知数，1/d[i]看做系数

把f[i]都移到左边，1/d 都移到右边

得到n个方程，高斯消元解出来

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define N 101#define M 10001const double eps=1e-7;int n;int d[N];int to[M<<1],nxt[M<<1],front[N],val[M<<1],tot;double a[N][N];int bit[31];void read(int &x){    x=0; char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}void add(int u,int v,int w){    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w;}void gauss(){    int r;    double f;    for(int i=0;i
          
           abs(a[r][i])) r=j; if(r!=i) swap(a[r],a[i]); for(int k=i+1;k
           
            =0;--i) { for(int j=i+1;j