zoj3591 Nim(Nim博弈)

题目意思是说有n堆石子，Alice只能从中选出连续的几堆来玩Nim博弈,现在问Alice想要获胜有多少种方法（即有多少种选择方式）。

方法是这样的，由于Nim博弈必胜的条件是所有数的抑或值不为0，证明见点击，所以答案就转化为原序列有多少个区间的亦或值为0，用n*(n+1) / 2 减去这个值就可以了。

而求有多少个区间的亦或值为0，实际上就是求对于亦或值的前缀nim[i]，满足nim[i] == nim[j] 的对数，这时只要对nim数组排序就可以算了

详见代码：

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define inf (-((LL)1<<40))

 #define lson k<<1, L, mid

 #define rson k<<1|1, mid+1, R

 #define mem0(a) memset(a,0,sizeof(a))

 #define mem1(a) memset(a,-1,sizeof(a))

 #define mem(a, b) memset(a, b, sizeof(a))

 #define FIN freopen("in.txt", "r", stdin)

 #define FOUT freopen("out.txt", "w", stdout)

 #define rep(i, a, b) for(int i = a; i <= b; i ++)

 template<class T> T CMP_MIN(T a, T b) { return a < b; }

 template<class T> T CMP_MAX(T a, T b) { return a > b; }

 template<class T> T MAX(T a, T b) { return a > b ? a : b; }

 template<class T> T MIN(T a, T b) { return a < b ? a : b; }

 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }

 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }

 //typedef __int64 LL;

 typedef long long LL;

 const int MAXN = ;

 const int MAXM = ;

 const double eps = 1e-;

 //LL MOD = 987654321;

 int n, a[MAXN], x, s, w, T;

 int main()

 {

     while(~scanf("%d", &T)) while(T--) {

         cin >> n >> s >> w;

         LL ans = (LL)n * (n + ) / ;

         int g = s;

         rep (i, , n) {

             x = g;

             if( x ==  )    { x = g = w; }

             if( g% ==  )  { g = (g/); }

             else            { g = (g/) ^ w; }

             a[i] = a[i - ] ^ x;

             if(a[i] == ) ans --;

         }

         sort(a + , a + n + );

         int num = ;

         rep (i, , n) {

             if(a[i] == a[i - ]) {

                 ans -= num;

                 num++;

             }

             else num = ;

         }

         cout << ans << endl;

     }

     return ;

 }