poj2975(nim游戏取法)

求处于必胜状态有多少种走法。

if( (g[i]^ans) <= g[i]) num++; //这步判断很巧妙

//
//  main.cpp
//  poj2975
//
//  Created by New_Life on 16/8/12.
//  Copyright © 2016年 chenhuan001. All rights reserved.
//

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int g[1010];

int main(int argc, const char * argv[]) {
    int n;
    while(cin>>n && n!=0)
    {
        int mark[20];
        memset(mark,0,sizeof(mark));
        int ans = 0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",g+i);
            ans ^= g[i];
        }
        if(ans == 0)
        {
            printf("0
");
            continue;
        }
        for(int i=0;i<31;i++)
        {
            if( ((1<<i)&ans)!=0 ) mark[i] = 0;
        }
        int num = 0;
        for(int i=0;i<n;i++) if( (g[i]^ans) <= g[i]) num++;
        printf("%d
",num);
    }
    
    return 0;
}