简单分析一下题意就是找出从$1$到$N$的最长$XOR$路径。
接着发现来回走对答案没有贡献,因此来回走=无效
那么只有进入了环,才有可能对答案产生贡献,但是环的数量太多了,怎么表示出来呢?
线性基即可,高斯消元求出基,基即可表示线性空间中的所有XOR值。
void insert(ll x)
{
for(int j=63;~j;j--)
if(x>>j&1)
{
if(!num[j])
{
num[j]=x;
return ;
}
x^=num[j];//高斯消元
}//保证只有num[j]这一个数有1<<j
}
0 条评论