P4151 [WC2011]最大XOR和路径 题解
题面
首先考虑没有环的情况，那么答案肯定就是 \(1\) 到 \(n\) 简单路径的边权异或和。如果出现环，设这个环边权异或和为 \(c\)，从这条 \(1\) 到 \(n\) 简单路径到这个环的路径边权异或和为 \(k\)，那么答案为 \(dis_n\oplus k\oplus c\oplus k\)。
通过上面的分析，可以发现，答案就是 \(dis_n\) 与所有环的异或和这些数能够异或起来的最大值，这显然可以使用线性基来快速解决。注意 \(dis_n\) 是任意一条 \(1\) 到 \(n\) 的路径异或和即可，因为如果还有其他路径，一定会出现在环的那部分内，贡献是一样的。复杂度 \(O(n\log v)\)。
点击查看代码
#include
#include
typedef long long ll;
inline ll rd(){
ll res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
const int N=1e5+13,M=62+13;
struct Onbase{
ll p[M];
inline void insert(ll x){
for(int i=62;i>=0;--i){
if(!(x&(1ll<=0;--i)
if((ans^Base.p[i])>ans) ans^=Base.p[i];
printf("%lld\n",ans);
return 0;
}