[HOJ 156] Xor路徑和

作法：

首先我們當然可以只看和$1,n$連通的分量就好了。考慮隨便取一條$1$走到$n$的路徑，設其 xor 值為$X$，然後隨便取一個圖中的圈，假設他邊的 xor 值為$Y$，那麼就存在一條從$1$走到$n$的路徑，使得其 xor 值為$X\; xor\;  Y$。因為只要在走原本的路徑時，走到一半分出去走到圈上的某一個點，繞完一圈後再沿原路走回來，再繼續走到$n$就可以了。因此我們的想法為：隨便取一條$1$走到$n$的路徑，並且找出所有圖中的圈，那麼只要想辦法用這條路徑的 xor 值加上隨便取幾個圈湊出最大的 xor 值就可以了。但這樣顯然會遇到圖中的圈太多的問題，但其實我們可以只保留那些「沒辦法被之前找到的圈的值 xor 出來的圈」就可以了，具體來說，如果有個圈$C$的 xor 值為$X$，並且存在其他圈$C_1,...,C_r$其 xor 值分別為$X_1,...,X_r$，那麼當$X=X_1\; xor \; ... \; xor \; X_r$時$C$就沒有用了，因為如果取到他的話就可以直接把他換成$C_1,...,C_r$（或是說我們取的圈的值都是線性獨立的）。再來注意到，我們考慮一條一條把邊加到圖中，那麼當某條邊$AB$加進去並且形成了新的圈時，我們隨便取一條$A$到$B$的路徑，和新加的這條邊組成了一個圈，那麼（不難證明）在這個圖中所有新形成的圈的 xor 值都可以用這個新的圈的 xor 值和舊的那些圈的值 xor 出來，因此我們就可以獲得至多$m$個圈的 xor 值，並且要想辦法把他刪成線性獨立的（這樣就會不超過 $60$ 個了）。

我們先看要怎麼知道這些圈的 xor 值是多少，事實上我們可以在維護 disjoint set 的時候順便維護這個點沿著他父親走到根，路上經過的邊的 xor 值是多少，只要修改一下 find 的過程就可以了，詳細可以參考 code 。再來則是我們想把$m$個數（向量）刪成線性獨立的$\leq 60$個，這只要直接高斯消去就可以了，細節在此省略。有了這些線性獨立的向量後，剩下的問題是：給定一個數$x$（也就是我們任意取的$1$走到$n$的路徑的 xor 值），我們要想辦法用這些向量 xor 一個數，使得他和$x$的 xor 值盡量大。我們可以考慮由高到低一位一位確定答案，舉例來說，$x$的二進制為$110101$，並且我們已經知道能湊出的盡量大的值為$101***$（後面代表還沒確定），那麼接下來我們想知道能不能用那些向量湊出形如$0110**$的向量，就能確定答案的下一位了。確定這個的方法只要把所有已有的向量的最後兩位砍掉，並且去處理「給定一些向量，是否有辦法湊出給定的某個向量」的問題就可以了，作法當然就直接高斯消去就可以了。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=100000+10,maxk=61 ;
 
vector<LL> bas ; /// basis
vector<LL> tmp(maxn) ;
bool gauss_elim(const vector<LL> &v0,LL val)
{
    if(v0.size()==60)
        for(int i=0;i<60;i++) tmp[i]=2*v0[i]+((val&(1LL<<i)) ? 1 : 0) ; /// 60 x 61
    else for(int i=0;i<v0.size();i++) tmp[i]=2*v0[i] ; /// get basis
    for(int i=0,j=60;j>0;j--)
    {
        int id=-1 ;
        for(int k=i;k<v0.size();k++) if(tmp[k]&(1LL<<j))
            {id=k ; break ;}
        if(id==-1) continue ;
        swap(tmp[i],tmp[id]) ;
        for(int k=id+1;k<v0.size();k++) if(tmp[k]&(1LL<<j))
            tmp[k]^=tmp[i] ;
        i++ ;
    }
    for(int i=0;i<60;i++) if(tmp[i]==1) return 0 ;
    return 1 ;
}
 
int fa[maxn] ;
LL fad[maxn] ;
int getfa(int x)
{
    if(fa[x]==x) return x ;
    int ret=getfa(fa[x]) ;
    fad[x]^=fad[fa[x]] ;
    return fa[x]=ret ;
}
LL join(int x,int y,LL dis)
{
    int x2=getfa(x) , y2=getfa(y) ;
    if(x2==y2) return fad[x]^fad[y]^dis ;
    fa[y2]=x2 ; fad[y2]=fad[x]^fad[y]^dis ;
    return -1 ;
}
 
int n ;
struct P{int x,y ; LL dis;};
vector<P> E ;
vector<int> v[maxn] ;
bool vis[maxn] ;
LL goald=-1 ;
void dfs(int x,LL nowd)
{
    if(x==n) goald=nowd ;
    for(auto i : v[x]) if(!vis[i])
    {
        vis[i]=1 ;
        int to=(E[i].x==x ? E[i].y : E[i].x) ;
        LL tmp=join(x,to,E[i].dis) ;
        if(tmp!=-1) bas.push_back(tmp) ;
        dfs(to,nowd^E[i].dis) ;
    }
}
 
vector<LL> hor(60),nowh(60) ;
main()
{
    int m ; scanf("%d%d",&n,&m) ;
    for(int i=0;i<m;i++)
    {
        int x,y ; LL dis ; scanf("%d%d%lld",&x,&y,&dis) ;
        E.push_back((P){x,y,dis}) ;
        v[x].push_back(i) ;
        v[y].push_back(i) ;
    }
    for(int i=1;i<=n;i++) fa[i]=i ;
    dfs(1,0) ;
 
    gauss_elim(bas,0) ;
    bas=tmp ;
    while(!bas.back()) bas.pop_back() ;
    for(auto &i : bas) i/=2 ;
 
    for(int i=0;i<bas.size();i++) for(int j=0;j<60;j++)
        if(bas[i]&(1LL<<j)) hor[j]|=(1LL<<i) ;
 
    LL ans=0 ;
    for(int i=59;i>=0;i--)
    {
        nowh[i]=hor[i] ;
        bool b=(goald&(1LL<<i)) ;
        if(gauss_elim(nowh,b ? ans : ans^(1LL<<i)))
            ans^=(b ? 0 : (1LL<<i)) ;
        else ans^=(b ? (1LL<<i) : 0) ;
    }
    printf("%lld\n",ans^goald) ;
}