Vasya has a sequence a consisting of n integers a1,a2,…,an. Vasya may pefrom the following operation: choose some number from the sequence and swap any pair of bits in its binary representation. For example, Vasya can transform number 6 (…000000001102) into 3 (…000000000112), 12 (…0000000011002), 1026 (…100000000102) and many others. Vasya can use this operation any (possibly zero) number of times on any number from the sequence.
Vasya names a sequence as good one, if, using operation mentioned above, he can obtain the sequence with bitwise exclusive or of all elements equal to 0.
For the given sequence a1,a2,…,an Vasya’d like to calculate number of integer pairs (l,r) such that 1≤l≤r≤n and sequence al,al+1,…,ar is good.
Input
The first line contains a single integer n (1≤n≤3⋅105) — length of the sequence.
The second line contains n integers a1,a2,…,an (1≤ai≤1018) — the sequence a.
Output
Print one integer — the number of pairs (l,r) such that 1≤l≤r≤n and the sequence al,al+1,…,ar is good.
Examples
inputCopy
3
6 7 14
outputCopy
2
inputCopy
4
1 2 1 16
outputCopy
4
Note
In the first example pairs (2,3) and (1,3) are valid. Pair (2,3) is valid since a2=7→11, a3=14→11 and 11⊕11=0, where ⊕ — bitwise exclusive or. Pair (1,3) is valid since a1=6→3, a2=7→13, a3=14→14 and 3⊕13⊕14=0.
In the second example pairs (1,2), (2,3), (3,4) and (1,4) are valid.
題意：
給你一個數組，有一種變換是可以交換這個數上所有的0和1的位置，比如3是00000000011,它可以變成…00100000001，…0000000011000…，問你有哪些區間可以通過異或操作變成0。
題解：
很明顯可以得出這樣的結論：區間至少有兩個數，區間所有1的和是偶數，區間最大值要小于等于區間其他數之和。
那麼我們通過dp[i][j]記錄目前位置i之前有多少累加為偶數和奇數的區間。
dp[i][0]就是偶數，dp[i][1]就是奇數，
那麼狀态轉移方程就是
if(a[i]%2==0)
dp[i][0]=dp[i-1][0]+1,dp[i][1]=dp[i-1][1];
else
dp[i][0]=dp[i-1][1],dp[i][1]=dp[i-1][0]+1;
當a[i]時偶數的時候，那麼就是前面偶數的區間+1，前面奇數的區間保持原樣，a[i]是奇數的時候，就是前面奇數的情況+1，前面偶數的情況變成奇數。
但是要注意區間最大值要小于等于區間其他數之和，但是這道題目每個數至少是1，是以隻需要找60+的範圍就好了，這裡面是偶數且最大值超過其他數的區間要剪掉，最後記得輸出long long
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e5+5;
int a[N],sum[N],dp[N][2];//dp[i][0]:num of even
int main()
{
int n;
scanf("%d",&n);
ll x;
for(int i=1;i<=n;i++)
{
scanf("%lld",&x);
int num=0;
while(x)
{
if((x&1))
num++;
x>>=1;
}
a[i]=num;
sum[i]=sum[i-1]+a[i];
}
ll ans=0;
for(int i=1;i<=n;i++)
{
if(a[i]%2==0)
dp[i][0]=dp[i-1][0]+1,dp[i][1]=dp[i-1][1];
else
dp[i][0]=dp[i-1][1],dp[i][1]=dp[i-1][0]+1;
if(a[i]%2)
ans+=dp[i-1][1];
else
ans+=dp[i-1][0];
int maxn=a[i];
for(int j=i-1;j>=max(1,i-70);j--)
{
int num=sum[i]-sum[j-1];
maxn=max(maxn,a[j]);
if(num%2==0&&maxn*2>num)
ans--;
}
}
return 0*printf("%lld\n",ans);
}