题解：P14994 异或最短路和

· · 题解

首先我们来分析一下异或最短路的性质。如果做过类似题目的可以快进到底下。

假设我们初始有一条 u\rightsquigarrow v 的路径。对于一个简单环 p_1,p_2,\dots,p_l，我们把我们的路径扩展为 u\rightsquigarrow v\rightsquigarrow p_1\to p_2\dots\to p_l\to p_1\rightsquigarrow v，其中 v\rightsquigarrow p_1 和 p_1\rightsquigarrow v 是同一段路径。这样的话因为这段路径被走了两次，其代价就被抵消了，于是这样一个扩展操作的效果是让路径的权值异或上了这个简单环的权值。

于是不难证明，只要我们初始找任意一条 u\rightsquigarrow v 的路径，然后经过若干次简单环的异或之后得到的最小值一定就是 u\rightsquigarrow v 的异或最短路。于是我们现在的问题就是如何找到任意一条 u\rightsquigarrow v 的路径的权值，以及如何表示所有简单环的权值能异或出的结果。

注意到后者问题的形式十分经典，我们可以考虑建出其异或线性基，即对于每一个简单环求出其权值然后全都放进线性基里。不过简单环的数量可能非常多。

根据某个神秘经典结论，随便取出一棵生成树之后，对于每一条非树边 (u,v) 考虑树上 u\leftrightsquigarrow v 这条路径以及这条边，记这种环为关于 (u,v) 的关键环，那么不难证明所有简单环都可以用这些关键环的对称差来表示出来（实际上直接在简单环上找出所有出现的非树边然后将其对应关键环全都拿出来做对称差即可）。

于是我们也顺便解决了第一个问题。给生成树随便取一个根，进行一遍 dfs 即可求出每个点 u 到根的路径上的边权异或和 d_u，那么树上 u\leftrightsquigarrow v 的路径的权值就是 d_u\oplus d_v。

于是我们的问题变为这样：

给定 n 个整数 d_i 以及一个线性基 F，记 x 选取一个 F 的子集并异或上去能得到的最小权值为 F(x)，求 \sum_i\sum_j F(d_i\oplus d_j)。

首先我们能发现一个很关键的性质：F(d_i\oplus d_j)=F(d_i)\oplus F(d_j)。

这个看上去并不是那么显然，为什么是对的呢？

可能存在比较严谨的线性代数证明，但是我线性代数很菜，这里给一个比较直观的理解方法：

::::info[证明] 考虑我们代码中建出线性基之后查询一个值 x 的异或最小值的过程：记第 i 位存储的为 p_i，那么我们从高到低枚举 i，如果 x 的第 i 位为 1 那么就令 x\gets x\oplus p_i。

不妨假设 p_i 满足对于任意 i\neq j,p_i\neq 0,p_j\neq 0，p_i 的第 j 位都不会是 1，即每一位都有一个支配范围，而且每一个可以支配自己的位都不会被其他位支配。

这样的话我们可以把过程化简为 F(x)=\bigoplus_{v_i(x)=1}p_i，这里 v_i(x) 表示 x 在二进制下第 i 位。因为如果一个位在扫到它的时候的取值与初始取值不同，说明它被别的位支配了，那这个时候 p_i=0，所以不会产生影响。

那么这个时候就容易得到 F(x\oplus y)=F(x)\oplus F(y)。

至此，要解决的就是如下问题了：

给定 n 个整数 a_i，求 \sum_i\sum_j(a_i\oplus a_j)。

直接对于每一位考虑贡献，假设有 c_i 个数在第 i 位为 1，那么答案就是 \sum_i 2^{i+1}c_i(n-c_i)。注意 (i,j) 和 (j,i) 需要各算一次，所以指数上是 i+1。

不过注意原图可能不连通，我们需要对每个连通块选一个根并求出所有的 d，并对这个连通块内所有环求出线性基，然后分别求出连通块内部两两异或和之和。

这道题就解决了，总复杂度 O(n\log V)。

struct three{int x,y,z;};

int n,m;
vector<three>G,V;
vector<pair<int,ll>>v[N];
int f[N];
int zx(int x){return x==f[x]?x:f[x]=zx(f[x]);}
void gt(){// 随便求出一个生成森林
    for(auto[x,y,z]:G){
        if(zx(x)==zx(y)){
            V.push_back({x,y,z});
            continue;
        }
        f[f[x]]=f[y];
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
}
ll d[N];
int frmc[N],cid;
void dfs(int now,int fa){// 计算 d
    frmc[now]=cid;
    for(auto[i,va]:v[now])if(i^fa)
        d[i]=d[now]^va,dfs(i,now);
}
struct xxj{// 线性基
    ll p[65];
    void ins(ll x){
        for(int i=63;~i;i--)if(x>>i&1){
            if(!p[i]){p[i]=x;break;}
            x^=p[i];
        }
    }
    ll qry(ll x){
        for(int i=63;~i;i--)if(x>>i&1)x^=p[i];
        return x;
    }
}bs[N];
vector<ll>vas[N];
ll cnt[N];
ll solve(vector<ll>a){// 计算 sum sum (a_i xor a_j)
    int l=a.size();
    for(int i=0;i<64;i++)cnt[i]=0;
    for(auto v:a)for(int i=0;i<64;i++)cnt[i]+=(v>>i&1);
    ll ans=0;
    for(int i=0;i<64;i++)(ans+=(1ll<<i)%mod*cnt[i]%mod*(l-cnt[i])*2)%=mod;
    return ans;
}

void __INIT__(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
void __SOLVE__(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        G.push_back({x,y,z});
    }
    for(int i=1;i<=n;i++)f[i]=i;
    gt();
    for(int i=1;i<=n;i++)if(!frmc[i])++cid,dfs(i,i);
    for(auto[x,y,z]:V)bs[frmc[x]].ins(d[x]^d[y]^z);
    for(int i=1;i<=n;i++)vas[frmc[i]].push_back(bs[frmc[i]].qry(d[i]));
    ll ans=0;
    for(int i=1;i<=cid;i++)(ans+=solve(vas[i]))%=mod;
    cout<<ans<<"\n";
}