codeforces 1058E (思维)-蒲公英云

codeforces 1058E (思维)

传送

题意：给n个数，每个数的二进制1都可以随意的换位置，问区间异或为0的有多少个

思路：该问题可以转化为他的充要条件：

1.区间1的个数为偶数

2.区间最大值不超过区间和的一半；

偶数区间个数可以用cnt[i][2]记录以1开始，1~i中偶数和奇数区间个数，

那么偶数区间就是假如现在前缀是偶数，那就加cnt偶数，反之加奇数。

因为偶数=偶-偶/奇减奇

对于不符合的，因为数是60位左右，所以最大值不超过60，假如有一个数是60那么其他数至少为1，这样往前遍历60来次

就足矣。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+10;
int cnt[N][2], num[N];
int main(){
    int n;
    //cout<<__builtin_popcount(1000000000000ll)<<endl;
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        ll t;
        scanf("%I64d", &t);
        //num[i]=__builtin_popcount(t);
        while(t){
            if(t&1) num[i]++;
            t>>=1;
        }
        //printf("%d ", num[i]);
    }
    //puts("");
    cnt[0][0]=1;
    ll ans=0, sum=0;
    for(int i=1; i<=n; i++){
        int s=0, mx=0;
        sum+=num[i];
        if(sum&1)
            ans+=cnt[i-1][1];
        else
            ans+=cnt[i-1][0];
        cnt[i][1]=cnt[i-1][1]+(sum&1);
        cnt[i][0]=cnt[i-1][0]+(sum%2==0);
        for(int j=i; j>0&&i-j+1<=63; j--){
            s+=num[j];
            mx=max(mx, num[j]);
            if(s%2==0 && mx>s-mx) ans--;
        }
    }
    printf("%I64d\n", ans);
    return 0;
}