[ARC173E] Rearrange and Adjacent XOR 题解

题目链接

点击打开链接

题目解法

太牛了！！！

这道题我的第一反应是从高位往低位确定，但这样就全错了
换个角度考虑，找最后的答案可以由那些数异或而成

这里给出结论：答案一定是偶数个数的异或和（在 \(n\%4=2\) 且 \(n\neq 2\) 时，不能由全集构成）
证明：

1. 选出的数非全集的情况
   用数学归纳法
   假设答案选的数为 \(a_1,...,a_{2k}\)（\(2k<n\)，顺序无所谓）
   如果 \(k\) 为偶数，我们构造顺序为 \(a_1,a_2,...,a_{2k},a_{2k+1},...,a_n\)，下一轮会变成选 \(k\) 个数（\(a_{2i-1}\oplus a_{2i}\;(1\le i\le k)\)）的子问题
   如果 \(k\) 为奇数，我们考虑带进来一个不需要的数，构造顺序 \(a_1,a_2,...,a_n,a_{2_k},a_{2k+1},...,a_{n-1}\)，下一轮会变成选 \(k+1\) 个数（\(a_{2i-1}\oplus a_{2i}\;(1\le i\le k-1),\;a_{2k-1}\oplus a_n,\;a_{2k}\oplus a_n\)）的子问题
2. 选出的数为全集的情况
   \(n\) 为奇数不用管
   如果 \(n=4k\)，我们构造 \(a_1,...,a_n\)，下一轮就是选出 \(2k\) 个数的非全集的子问题了
   如果 \(n=4k+2\)，考虑证明下一轮必须选出 \(q=2k+1\) 个数
   若 \(q<2k+1\)，则数一定选不全
   若 \(q>2k+1\)，则数一定会抵消
   所以下一轮选的数为奇数，不合法

如果没有数必须不选的情况考虑线性基，把 \(a_i\oplus a_{i+1}\) 都塞到线性基中，然后选出的数一定是偶数个
有数必须不选的话，不带那个数跑一遍线性基即可

时间复杂度 \(O(n^2\log V)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=110;
int n;
LL a[N],b[N],base[60];
void ins(LL v){
    DF(i,59,0) if(v>>i&1){
        if(!base[i]){ base[i]=v;break;}
        v^=base[i];
    }
}
int main(){
    read(n);
    F(i,1,n) read(a[i]);
    LL ans=0;
    if(n==2||n%4==0) F(i,1,n) ans^=a[i];
    F(i,1,n){
        int len=0;
        F(j,1,n) if(i!=j) b[++len]=a[j];
        ms(base,0);
        F(j,1,len-1) ins(b[j]^b[j+1]);
        LL val=0;
        DF(j,59,0) if(!(val>>j&1)) val^=base[j];
        chkmax(ans,val);
    }
    printf("%lld\n",ans);
    return 0;
}