ZOJ 3591 Nim （NIM博弈+统计

转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

题目：按照某种规律生成一个序列，选中某段连续的序列玩NIM游戏，先手能必胜的有多少种。

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4675

乍一看毫无头绪啊。序列貌似会形成循环，可是数量如此之大。

先按照规则生成序列。保存前i个堆的异或值，存在nim[i]。

如果想要必胜，是选中连续的数异或不为0，如果存在nim[i]==nim[j]则表示i+1,i+2……j的异或值0,则是一组必败的局面。

这样我们便想到从对立而考虑，总共的选择是n*(n+1)/2。

将nim排序，找出相同 的nim值有多少个，便可以统计出有多少必败的局面。

同时注意nim[i]为0的话，现在从1----i便是必败局面，也要减掉。

另外注意int溢出

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<vector>
#define C    240
#define TIME 10
#define inf 1<<25
#define LL long long
using namespace std;
int a[100005],nim[100005];
int main(){
    int t,n,s,w;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&s,&w);
        int g=s,ret=0;
        for(int i=0;i<n;i++){
            a[i]=g;
            if(a[i]==0)  a[i]=g=w;
            if(g%2==0)  g/=2;
            else g=(g/2)^w;
            ret^=a[i];
            nim[i]=ret;
        }
        sort(nim,nim+n);
        LL sum=(LL)n*(n+1)/2;
        int len=1;
        for(int i=1;i<n;i++){
            if(nim[i]==nim[i-1])
                len++;
            else{
                if(nim[i-1]==0)
                    sum-=len;
                sum-=(LL)len*(len-1)/2;
                len=1;
            }
        }
        sum-=(LL)len*(len-1)/2;
        printf("%lld\n",sum);
    }
    return 0;
}