题解 | #踩不出足迹#

【C.踩不出足迹】题解

通过题目我们可以知道对于每到达一个数我们都会有两种操作

异或
同或

我们来看同或的性质，就拿题目给出的样例来说 $(000) (101)=(010)$ ，经观察发现，这种操作等价于异或操作 $+$ $k$ 位取反操作。

知道这个性质之后，发现每次操作都会异或，不同的是是否选择将 $k$ 位进行取反操作。因为异或存在交换律，所以我们可以将所有取反操作拿到最后，由于相同的数异或偶数次等于没有异或，所以我们只有取反或者不取反两种选择。

所以答案就是 $\max\{sum,sum\bigoplus p\}$ 其中 $sum$ 为前缀疑异或和

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int unsigned long long
using namespace std;
const int B=1e6+10;
int n,k;
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
    return x * f;
}
void Print(int x) {if(x < 0) putchar('-'), x = -x; if(x > 9) Print(x / 10); putchar(x % 10 ^ 48);}
int mul(int a,int b) 
{
    int res=1;
    while (b)
    {
        if (b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
signed main()
{
    n=read(),k=read();
    int s=mul(2,k)-1;
    int sum=0;
    for (int i=1;i<=n;i++)
    {
        int x=read(); 
        sum^=x;
    }    
    int p=sum^s;
    if (sum<p) Print(p);
    else Print(sum);
}
/*
2 64
18446744073709551615 18446744073709551615
*/