题解 | #活着的证据#

【C.踩不出足迹】题解
看见其他大佬的题解，都是得出了一个简单的结论。我来讲讲我的。
我们分开考虑0~k-1位二进制数，想要结果最大，最终运算出来的结果第k-1位必然为1，我们任取一种运算方式(比如在代码中，我让前n-1个数字异或，判断和最后一个数字是同或还是异或)，使得k-1位为1。
emm之后我们考虑其他位的数(0 ~ k-2) ,若按照上述任取的运算方式，计算出的答案为0，我们考虑在不影响高位的情况下，修改运算方式，使得该位变为1. 事实证明，这是无法完成的。因为若要修改一位上的数⇔修改奇数个运算符号,因此修改该位的运算结果必然会影响到高位。

所以算法很简单,只需要根据第k-1位确定出运算方式，然后每位按照同样的方式计算即可,注意用unsigned long long

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef  long long ll;
const int N = 2000010 ,M = 1000010,mod = 998244353;
int n,m,d,k;
ull a[N],jie[100];
int res[N];
signed main()
{
    jie[0] = 1;
    for(int i=1;i<=63;i++) jie[i] = jie[i-1]*2;
    cin>>n>>k;k--;
    for(int i=1;i<=n;i++) scanf("%llu",&a[i]);
    int z = 0;
    for(int i=1;i<n;i++)
        z^=(a[i]>>k&1);
    bool f = z==(a[n]>>k&1);//确定最后一个数是异或还是同或，若f位true则为同或 
    ull res = 0;
    for(int i=k;i>=0;i--)//按位 运算即可 
    {
        int z = 0;
        for(int j=1;j<n;j++)
            z^=(a[j]>>i&1);

        if(!f) z^=(a[n]>>i&1);//异或 
        else
            z = z==(a[n]>>i&1);//同或 
        if(z)
            res+=jie[i];
    }
    cout<<res;
    return 0;
}