一道ACM题目，求大神解决
Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap. Here is another version of Nim game. There are N piles of stones on the table. Alice first chooses some CONSECUTIVE piles of stones to play the Nim game with Tom. Also, Alice will make the first move. Alice wants to know how many ways of choosing can make her win the game if both players play optimally.

You are given a sequence a[0],a[1], ... a[N-1] of positive integers to indicate the number of stones in each pile. The sequence a[0]...a[N-1] of length N is generated by the following code:



int g = S;
for (int i=0; i<N; i++) {
a[i] = g;
if( a[i] == 0 ) { a[i] = g = W; }
if( g%2 == 0 ) { g = (g/2); }
else { g = (g/2) ^ W; }
}

Input

There are multiple test cases. The first line of input is an integer T(T ≤ 100) indicates the number of test cases. Then T test cases follow. Each test case is represented by a line containing four integers 3 integers N, S and W, separated by spaces. (0 < N ≤ 105, 0 < S, W ≤ 109)
Output

For each test case, output the number of ways to win the game.
Sample Input

2
3 1 1
3 2 1

Sample Output

4
5

O(n^2)的复杂度会超时
下面是我的代码

#include<iostream>
#include<stdio.h>
#include<memory.h>
using namespace std;
#define MAX 100010
int a[MAX];
int main()
{
int i,j;
int t,g;
int sum;
int ma;
int N,S,W;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&N,&S,&W);
g = S;
sum=0;
for (i=0;i<N; i++)
{
a[i] = g;
if(!a[i])
{
a[i] = g = W;
}
if(!(g&1))
{
g = (g>>1);
}
else
{
g = (g>>1) ^ W;
}
ma=0;
for(j=i;j>=0;j--)
{
ma=ma^a[j];
if(ma)
sum++;
}
}

printf("%d\n",sum);
}
return 0;
}
会超时，求解决

[解决办法]
就是把c[j]=nim[0~j]和之前的所有c[i]=nim[0~i]做比较，假设有k个c[i]（i<j）和c[j]相同，那么把答案加上j-k。
判断比较不用for(i=0;i<j;i++)。用哈希表的话就O(1)了。然后整个的复杂度O(n)
[解决办法]
允许在连续的区间当中拿掉一个，从而使得区间数+1吗？