Hackerrank hourrank 19
What Are the Odds?
传送门
题目大意：
两个人在玩一个叫做Nim game（n堆石头，每个人每次从一堆中选择一个或多个石头移走，最后不能移动的人输）的游戏，他们把这个游戏更改了一下，每次在游戏前先移除[L,R]区间内的石子(L<=R)，然后进行游戏，问有多少种方法使得后手必胜(n<=5*10^5)

Solution：
刚看到题的时候想了好久必胜策略是啥，后来才知道原来这是一个经典的Nim game模型（不知道的可以百度一下，百科里面很详细），这里我就说一下结论吧，当每堆石子数的异或和为0时，后手必胜，所以说我们的问题就变成了一个数列去掉一段区间后异或和为0的方案数是多少，n^2的做法很显然，所以说我们考虑优化：记一个数组q[i]表示从第i+1~第n项的异或和，pre[i]表示前i项的异或和，那么q[i]=pre[n]^pre[i]，q可以通过pre O(1) 求出，然后我们对于每个q[i]，求和它的值相同的pre[j]且j

#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;
int n,a[500010],x=0;
int sum[500010];
long long ans=0;
vector<int> f[500010];
int main()
{
    scanf("%d",&n);
    f[0].push_back(0);//这步容易被忽视
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]),sum[i]=sum[i-1]^a[i],f[sum[i]].push_back(i);
    for (int i=1;i<=n;i++)
    {
        int x=sum[i]^sum[n];
        if (f[x].empty()) continue;
        int as=-1;
        int l=0,r=f[x].size()-1;
        while (l<=r)
        {
            int mid=l+r>>1;
            if (f[x][mid]<=i-1)
                {as=mid,l=mid+1;}
            else r=mid-1; 
        } 
        ans+=as+1;
    }
    printf("%lld",ans);
}