CF1030E-Vasya and Good Sequences

2022-08-12 题解

题目大意：给定一个数列a[]，里面的所有数都可以变成所有二进制位上的1个数相同的任意其它数。问a[]有多少个子段的异或和可以为0。

由于里面所有数都能变成与其二进制位相同的任何数，只用关心每个数的二进制表示中含有多少个1即可。

这里选用__builtin_popcount()来计算一个数的二进制中含有的1数量。数非常大，应当使用__builtin_popcountll()。

不难想到，对于一个子段，其中任意原本属于两个数的1可以相互抵消。基于此想法，一个子段异或和为0的条件如下：

其中所有数的二进制表示的1的数量的总和必须是偶数。

这一点比较好理解。如果1的数量是奇数，总会有某一位上的二进制1数量是奇数个，最终异或和不可能为0。
子段内1最多的数，1的数量不能超过子段内所有数1的数量总和的一半。

如果不满足这个条件，剩下的数不论怎么组合，都不能将最大数抵消。

如果满足了这两个条件，就可以通过每次选择子段中最大的两个数，将它们抵消掉1，进而抵消掉子段中所有数。

当然，其实并不需要关心是如何抵消掉的。所以只要子段满足上面的两个条件即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int pre[2] = {1}, a[300005];
signed main()
{
    int n;
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
    {
        int t;
        scanf("%lld", &t);
        a[i] = __builtin_popcountll(t);
    }
    int res = 0, sum = 0;
    for (int i = 1; i <= n; i++)
    {
        sum += a[i];
        res += pre[sum & 1];
        pre[sum & 1]++;
        int maxx = -1e9, num = 0;
        for (int j = i, t = 1; t <= 64 && j; j--, t++)
        {
            num += a[j];
            maxx = max(maxx, a[j]);
            if ((num & 1 ^ 1) && (maxx << 1) > num)
                res--;
        }
    }
    printf("%lld", res);
    return 0;
}