$\mathcal{Description}$

Link.

给定 $n$ 个点 $m$ 条边的连通无向图 $G$，边有边权。其中 $u,v$ 的距离 $d(u,v)$ 定义为 $u$ 到 $v$ 的最大异或路径。还有 $q$ 次询问，每次给出 $l,r$，求 $\bigoplus_{l\le i<j\le r}d(i,j)$。

$n,m,q\le10^5$，边权 $w<2^{30}$。

$\mathcal{Solution}$

首先必然套用这个经典永流传的结论：设所有环的异或和构成空间 $V$，$d'(u,v)$ 为 $u$ 到 $v$ 的任意一条路径的异或和，则 $d(u,v)=\max\{d'(u,v)\oplus x\mid x\in V\}$。

记变换 $F_V:x\rightarrow \max\{x\oplus v\mid v\in V\}$，由于它不具有线性性，我们拆开 $d(u,v)$ 的 $\max$ 进行优化就显得困难。不过，考查与之类似的另一个变换 $G_V:x\rightarrow\min\{x\oplus v\mid v\in V\}$，能够证明 $G_V$ 是线性变换，且会得到一个炫酷的结论：$F_V(x)=G_V(x)\oplus\max\{v\mid v\in V\}$。

证明

把 $x$ 等元素视为 $U=\{0,1\}^k$ 下的向量。设 $\boldsymbol x=\begin{pmatrix}x_0& x_1&\cdots& x_{k-1}\end{pmatrix}$，取 $U$ 的子空间 $V$ 的线性基 $\mathcal B$，令
$$
\mathcal B=\begin{pmatrix}\boldsymbol b_0\\ \boldsymbol b_1\\ \vdots \\ \boldsymbol b_{k-1}\end{pmatrix},
$$
其中 $\boldsymbol b_i=\begin{pmatrix} b_{i,0} & b_{i,1}&\cdots& b_{i,k-1} \end{pmatrix}$，且有 $\forall j\lt i,b_{i,j}=0$。此时考虑 $\boldsymbol x\mathcal B^T$ 的意义：若 $\boldsymbol x$ 某一分量为 $1$，则加上（即异或上）线性基中的对应向量，很显然就是在线性基中构造 $\min\{x\oplus v\mid v\in V\}$ 的方式，所以 $G_V$ 是一个线性变换。 $\square$

“炫酷结论”就不证了，自证不难。

回到题目，处理一下式子：

\[\begin{aligned}\bigoplus_{l\le i<j\le r}d(i,j) &= \bigoplus_{l\le i<j\le r}d'(i,j)\oplus G_V(d'(i,j))\oplus \max\{v\mid v\in V\}\\&= \left(\binom{r-l+1}{2}\otimes\max\{v\mid v\in V\}\right)\oplus G_V\left( \bigoplus_{l\le i<j\le r}d'(i,j) \right).\end{aligned}
\]

抵消掉大量重复异或之后直接计算即可。复杂度 $\mathcal O(n+(m+q)\log w)$。

$\mathcal{Code}$

/*~Rainybunny*/

#include <bits/stdc++.h>

#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )

#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )

const int MAXN = 1e5;

int n, m, q, ecnt, head[MAXN + 5], dis[MAXN + 5];

bool vis[MAXN + 5];

struct Edge { int to, val, nxt; } graph[MAXN * 2 + 5];

struct XorLinearBasic {

    static const int W = 30;

    int bas[W];

    inline void insert( int v ) {

        per ( i, W, 0 ) if ( v >> i & 1 ) {

            if ( !bas[i] ) return void( bas[i] = v );

            v ^= bas[i];

        }

    }

    inline int ask( int v, const bool tar ) {

        per ( i, W, 0 ) if ( ( v >> i & 1 ) != tar ) v ^= bas[i];

        return v;

    }

} xlb;

inline void link( const int u, const int v, const int w ) {

    graph[++ecnt] = { v, w, head[u] }, head[u] = ecnt;

    graph[++ecnt] = { u, w, head[v] }, head[v] = ecnt;

}

inline void getCir( const int u ) {

    vis[u] = true;

    for ( int i = head[u], v; i; i = graph[i].nxt ) {

        if ( vis[v = graph[i].to] ) {

            xlb.insert( dis[u] ^ dis[v] ^ graph[i].val );

        } else {

            dis[v] = dis[u] ^ graph[i].val, getCir( v );

        }

    }

}

int main() {

    std::ios::sync_with_stdio( false ), std::cin.tie( 0 );

    std::cin >> n >> m >> q;

    rep ( i, 1, m ) {

        int u, v, w; std::cin >> u >> v >> w;

        link( u, v, w );

    }

    getCir( 1 );

    rep ( i, 1, n ) dis[i] ^= dis[i - 1];

    for ( int l, r; q--; ) {

        std::cin >> l >> r;

        std::cout << xlb.ask( ( r - l ) & 1 ? dis[r] ^ dis[l - 1] : 0,

          ( r - l + 1ll ) * ( r - l ) >> 1 & 1 ) << '\n';

    }

    return 0;

}

巴特西

Solution -「Gym 102956F」Find the XOR

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章