BZOJ4245: [ONTAK2015]OR-XOR

Description

给定一个长度为n的序列a[1],a[2],...,a[n]，请将它划分为m段连续的区间，设第i段的费用c[i]为该段内所有数字的异或和，则总费用为c[1] or c[2] or ... or c[m]。请求出总费用的最小值。

Input

第一行包含两个正整数n,m(1<=m<=n<=500000)，分别表示序列的长度和需要划分的段数。

第一行包含n个整数，其中第i个数为a[i](0<=a[i]<=10^18)。

Output

输出一个整数，即总费用的最小值。

Sample Input

3 2
1 5 7

Sample Output

HINT

第一段为[1]，第二段为[5 7]，总费用为(1) or (5 xor 7) = 1 or 2 = 3。

按位枚举，考虑答案的第i位能否为0。

判定是否同时满足两个条件：1.所有A在第i位的异或和为0（因为x|y>=x^y）2.将异或和在i位上异或和为0且在前面位上异或和与答案相符的作为一段，判定是否划分出的段数>=m。

#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
typedef long long ll;
inline ll read() {
    ll x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
const int maxn=500010;
ll n,m,A[maxn],mark[maxn];
int check(ll ans,int p) {
    ll v=0;int cnt=0;
    rep(i,1,n) {
        v^=A[i];
        if(!(v>>p&1)&&!mark[i]) cnt++;
    }
    v=0;
    if(cnt>=m) rep(i,1,n) {
        v^=A[i];
        if(v>>p&1) mark[i]=1;
    }
    return cnt>=m;
}
int main() {
    n=read();m=read();ll v=0,ans=0;
    rep(i,1,n) v^=(A[i]=read());
    dwn(i,62,0) if(v>>i&1||!check(ans,i)) ans|=1ll<<i;
    printf("%lld
",ans);
    return 0;
}

View Code