G - Minimum XOR Walk 解説 by en_translator
Let \(W_e\) denote the weight of edge \(e\). Set \(L=30\).
Fix a spanning tree \(T\), and let \(A_v\) be the weight of the simple path between vertices \(1\) and \(v\) in \(T\).
For an edge \(e\) connecting vertices \(u\) and \(v\), the walk \((v_1,e_1,v_2,\dots,v_{k-1},e_{k-1},v_k)\) has a weight \(A_{v_1}\oplus W'_{e_1}\oplus \cdots \oplus W'_{e_{k-1}}\oplus A_{v_k}\).
Meanwhile, \(W'_e=0\) for all edges \(e\) in \(T\), so for all vertices \(u\) and \(v\) and a sequence of edges \(e_1,\dots,e_l\), there exists a walk between \(u\) and \(v\) with weight \(A_u\oplus W'_{e_1} \oplus \cdots \oplus W'_{e_l} \oplus A_v\).
Defining \(X=\{W'_e\mid e\in E(G)\}\), the problem is reduced to as follows:
- You are given a sequence of non-negative integers \((A_1,\dots,A_N)\), a non-negative integer \(K\), and a set of non-negative integers \(X\).
- Find the number of integer pairs \((i,j)\ (1\leq i\lt j\leq N)\) such that \(\min\{A_i \oplus A_j \oplus w_1\oplus\cdots \oplus w_k \mid w_1,\dots,w_k \in X\}\leq K\).
Let \(F(x)=\{x\oplus w_1\oplus\cdots \oplus w_k \mid w_1,\dots,w_k \in X,k\geq 0\},f(x)=\min F(x)\). \(f(x)\) can be computed in \(O(L)\) time for any given \(x\), by precomputing the XOR (exclusive or) basis of \(\operatorname{span} X\) in \(O(NL)\) time.
Here, we claim that \(f(x\oplus y)=f(x)\oplus f(y)\) for all non-negative integers \(x\) and \(y\).
Proof
Take an XOR basis $B$ of $\operatorname{span} X$ whose most significant bits have different places. By definition of $f$, it immediately follows that $f(x\oplus y) \leq f(x)\oplus f(y)$. If we assume $f(x\oplus y) \lt f(x)\oplus f(y)$, we have the following representation using pairwise distinct elements $b_1,\dots,b_k\ (k\geq 1)$ of $B$: $$f(x\oplus y)\oplus f(x)\oplus f(y)=b_1 \oplus \cdots \oplus b_k.$$ Let $b=\max\{b_1,\dots,b_k\}$, and assume that the most significant bit of $b$ is at $2^i$s place. Then by definition of $b$, the most significant bit of the right hand side of the equation above is also at $2^i$s place. By $f(x\oplus y)\lt f(x)\oplus f(y)$, the digits at $2^i$s place of $f(x\oplus y)$ and $f(x)\oplus f(y)$ are $0$ and $1$, respectively. Hence, the digits of $f(x)$ and $f(y)$ at $2^i$s place are different. By symmetry, we may assume that $f(x)$ has $1$ at $2^i$s place. Then $f(x)\oplus b \lt f(x)$ and $f(x)\oplus b \in F(x)$, but this contradicts $f(x)=\min F(x)$. Therefore, by contradiction we obtain $f(x\oplus y)=f(x)\oplus f(y)$. (End of proof)Therefore, by defining \(B_i=f(A_i)\) the problem is reduced as follows:
- You are given a sequence of non-negative integers \((B_1,\dots,B_N)\) and a non-negative integer \(K\).
- Find the number of integer pairs \((i,j)\ (1\leq i\lt j\leq N)\) such that \(B_i\oplus B_j\leq K\).
By using a Binary Trie constructed from the most significant bits, the problem can be solved in a total of \(O(NL)\) time.
投稿日時:
最終更新: