首先,我们可以从高到低枚举,看这一位是否可以通过一个分割,使得每一块的异或和在这一位上都为0。
这个贪心显然是正确的。
我们设这个序列的前缀异或和为(xs),前(i)个数(从第一个开始)的前缀异或和二进制的第(j)位(从第0位开始)为(xs_{i,j})。
设当前位为(i)
则如果一段区间([l,r])的异或和为0那么有(xs_{r,i}oplus xs_{l-1,i}=0)
显然任意一种分割方案中,第1个数始终是一个区间的左端点,所以我们需要第1段区间的右端点(p)满足(xs_{p,i}=xs_{0,i}=0)。
由于序列必然首尾相接,那么也就要求所有区间的右端点(p)都有(xs_{p,i}=0)。
所以序列中可以作为右端点的位置数量为满足(xs_{p,i}=0(0<ple n))的(p)的数量,显然数量需要大于等于(m)。
当然,第(n)个位置必然是某一个区间的右端点,还要满足(xs_{n,i}=0)。
如果满足上述条件,那么这一位就可以为(0)。
真的吗?
其实我们还需要满足比第(i)位高的那些位的条件。
所以我们记录(u_{i})表示要满足之前的位的限制,第(i)位是否可以作为区间的右端点,(u_i=1)表示可以,(u_i=0)表示不可以。
那么第(i)位可以为0的条件如下:
(xs_{n,i}=0)
(sum_{p=1}^n[xs_{p,i}=0 exttt{且}u_p=1]ge m)
如果第(i)位可以为0,我们还需要更新(u),如果(xs_{p,i}=1),那么(u_p=0)。
code:
#include<bits/stdc++.h>
using namespace std;
int n,m,tot,p[500010],len;
long long sum[500010],ans;
void scan(long long&x){
x=0;
char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scan(sum[i]);
while((1ll<<len)<sum[i])++len;
sum[i]^=sum[i-1],p[i]=1;
}
for(int i=len;i>=0;--i,tot=0){
if(sum[n]&(1ll<<i)){
ans|=1ll<<i;
continue;
}
for(int j=1;j<=n;++j)tot+=p[j]&&!(sum[j]&(1ll<<i));
if(tot>=m)for(int j=1;j<=n;++j)p[j]&=!(sum[j]&(1ll<<i));
else ans|=1ll<<i;
}
printf("%lld",ans);
return 0;
}