zoj 3591 Nim

Nim

Time Limit: 3 Seconds Memory Limit: 65536 KB

Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps. The game ends when one of the players is unable to remove object in his/her turn. This player will then lose. 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 3 integers N, S and W, separated by spaces. (0 < N ≤ 10⁵, 0 < S, W ≤ 10⁹)

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

Author: CAO, Peng
Contest: The 12th Zhejiang University Programming Contest

题意：有n堆火柴，选择连续的火柴堆进行Nim游戏，问先手获胜有多少种方案。

分析：如果是普通的Nim游戏，那么就是对每个火柴堆取异或，如果先手要赢，那么异或的值就要非0。那么题目就变成在N个火柴堆里面有多少个连续火柴堆异或值非0。一开始的思路是最简单粗暴的枚举区间，但是N^2的复杂度显然是过不了的，所以这里用a[i]保存从第一个数到第i个数的异或值，那么第i到j堆的异或值为a[j]^a[i-1]，由于非零情况多不好求，于是取对立情况即两个相等的数异或为0那么先手就会输，题目就变成了有多少个a[i]相等，就相当于是求出了原数组里面是有多少个连续的区间。做法是排序之后扫一遍看有多少个相等。1~n的连续区间个数是n*(n+1)/2，如果有x个相同的值的话，减去x*(x-1)/2即可，注意0要另外减去0的个数，因为0代表1~x这个区间先手必败。

注意答案要用long long

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#define LL long long
using namespace std;
const int MAXN=100000+5;
int kase,N,S,W,d;
int vv[MAXN],a[MAXN];

int main()
{
    scanf("%d",&kase);
    while(kase--)
    {
        scanf("%d %d %d",&N,&S,&W);
        memset(vv,0,sizeof(vv));
        memset(a,0,sizeof(a));

        int g=S,d=0;
        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; }
            d^=a[i];
            vv[i]=d;
        }
        sort(vv,vv+N);
        LL sum=(LL)N*((LL)N+1)/2;
        LL len=1;
        for(int i=1;i<N;i++)
        {
            if(vv[i]==vv[i-1])
                len++;
            else
            {
                if(vv[i-1]==0)
                    sum-=len;
                sum-=(len-1)*len/2;
                len=1;
            }
        }
        sum-=(len-1)*len/2;
        printf("%lld
",sum);
    }
    return 0;
}

View Code