正题

题目链接:https://www.luogu.com.cn/problem/P3211

---

一个\(n\)个点\(m\)条边的无向图，从\(1\)到\(n\)随机游走。求期望路径异或和。

\(2\leq n\leq 100,1\leq m\leq 10^4\)

---

因为是异或的期望，很难直接处理，所以考虑按位考虑每一位是\(1\)的概率。

然后\(n\)很小就是一个很显然的高斯消元了。设\(f_i\)表示\(i\sim n\)是\(1\)的概率。

\[f_x=\frac{1}{deg_x}(\sum_{x->y,w=1}(1-f_y)+\sum_{x->y,w=0}f_y)
\]

时间复杂度\(O(n^3\log w_i)\)

---

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110;
struct node{
    int to,next,w;
}a[N*N*2];
int n,m,tot,deg[N],ls[N];
double f[N],ans;
void addl(int x,int y,int w){
    a[++tot].to=y;
    a[tot].next=ls[x];
    ls[x]=tot;a[tot].w=w;
    return;
}
namespace G{
    double a[N][N],b[N];
    void init(){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++)a[i][j]=0;
            b[i]=0;
        }
        return;
    }
    void solve(double *f){
        for(int i=1;i<=n;i++){
            int z=i;
            for(int j=i+1;j<=n;j++)
                if(a[j][i]>a[z][i])z=i;
            swap(a[i],a[z]);swap(b[i],b[z]);
            double inv=a[i][i];
            for(int j=i;j<=n;j++)
                a[i][j]=a[i][j]/inv;
            b[i]=b[i]/inv;
            for(int j=i+1;j<=n;j++){
                double rate=-a[j][i];
                for(int k=i;k<=n;k++)
                    a[j][k]+=a[i][k]*rate;
                b[j]+=b[i]*rate;
            }
        }
        for(int i=n-1;i>=1;i--){
            for(int j=i+1;j<=n;j++)
                b[i]-=b[j]*a[i][j]/a[j][j];
            f[i]=b[i];
        }
        return;
    }
};
void solve(int w){
    G::init();G::a[n][n]=1;
    for(int x=1;x<n;x++){
        for(int i=ls[x];i;i=a[i].next){
            int y=a[i].to;
            if(a[i].w&w)G::a[x][y]++,G::b[x]++;
            else G::a[x][y]--;
        }
        G::a[x][x]+=deg[x];
    }
    G::solve(f);ans+=(double)w*f[1];
    return;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        deg[x]++;addl(x,y,w);
        if(x!=y)deg[y]++,addl(y,x,w);
    }
    for(int i=0;i<=30;i++)
        solve(1<<i);
    printf("%.3lf\n",ans);
    return 0;
}