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
",sum);
    }
    return 0;
}