首先,我们可以从高到低枚举,看这一位是否可以通过一个分割,使得每一块的异或和在这一位上都为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<p\le 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\texttt{且}u_p=1]\ge m\)

如果第\(i\)位可以为0,我们还需要更新\(u\),如果\(xs_{p,i}=1\),那么\(u_p=0\)。

code:

#include
    
     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<
     
      
       =0;--i,tot=0){        if(sum[n]&(1ll<
       
        =m)for(int j=1;j<=n;++j)p[j]&=!(sum[j]&(1ll<