题目描述
题解
一道看了题解很好懂但是自己死都想不出来的题 。
在这里，对于某一个数字取反相当于这个数 ? 2 k ? 1 ?2^k-1 ?2k?1。
我们知道，一道题目可以转化为有多少个前缀和的 l l l和 r r r满足 s u m r ? s u m l ? 1 = 0 sum_r?sum_{l-1}=0 sumr??suml?1?=0.
我们可以一次枚举每一个 r r r，如果 s u m i ? 1 ? a i sum_{i-1}?a_i sumi?1??ai?的个数比较小，则 s u m i = s u m i ? 1 ? a i sum_i=sum_{i-1}?a_i sumi?=sumi?1??ai?,并统计这样的数字有多少个，并累加答案。否则累加 s u m i ? 1 ? a i ? ( 2 k ? 1 ) . sum_{i-1}?a_i?(2^k-1). sumi?1??ai??(2k?1).
我们考虑一下，对于相同的 s u m i sum_i sumi?有 c n t 1 cnt1 cnt1个， s u m i ? ( 2 k ? 1 ) sum_i?(2^k-1) sumi??(2k?1)有 c n t 2 cnt_2 cnt2?个，显然答案是： C c n t 1 2 + C c n t 2 2 C_{cnt1}^{2}+C_{cnt2}^{2} Ccnt12?+Ccnt22?
所以 c n t 1 cnt1 cnt1和 c n t 2 cnt2 cnt2尽可能接近就可以让答案尽可能小。因此我们的每一步都要选较小的。
我们思考这样的每一步能优就优的贪心策略为什么不会对后面的决策产生影响的，思考一下，每一步对异或数组异或了一个 ( 2 k ? 1 ) (2^k-1) (2k?1),对于每一个 s u m i sum_i sumi?只有前i个数字异或起来和异或了一个 ( 2 k ? 1 ) (2^k-1) (2k?1),因为同一个数字异或两遍相当于没有异或。因此当前做了那种决策，对于下一步都是不受影响的。
最后我们用总个数 n × ( n + 1 ) 2 ? 异 或 和 为 0 的 方 案 数 \frac{n\times (n+1)}{2}-异或和为0的方案数 2n×(n+1)??异或和为0的方案数 即可。
小坑点： c n t 0 = 1 cnt_0=1 cnt0?=1,一开始异或和为 0 0 0.(卡了我好久)
代码如下：
#include <bits/stdc++.h>#define int long longusing namespace std;
const int N = 300000;int n, k;
int a[N], sum[N];
long long ans = 0;map <int,int> cnt;signed main(void)
{
cin>>n>>k;for (int i=1;i<=n;++i)scanf("%lld", a+i);cnt[0] = 1;for (int i=1;i<=n;++i){
sum[i] = sum[i-1] ^ a[i];int num1 = sum[i], num2 = sum[i] ^ ((1<<k)-1);if (cnt[num1] >= cnt[num2]) {
ans += cnt[num2] ++;sum[i] = num2;}else ans += cnt[num1] ++;}cout<<1LL * n * (n+1) / 2 - ans<<endl;return 0;
}