【POJ 2975】 Nim 博弈论

题目

给定 n 堆石子，分别有a1,a2,...,an个.

问有多少种方法使得第一次操作是必胜决策.

1≤n≤1000

分析

先求出异或值 x=a1⊗a2⊗...⊗an .

所以 x⊗a1⊗a2⊗⋯⊗an=0

只要将 x 与其中一个ai组合即可.

然而对于 ai ，取之后必然越来越小，所以要 ai⊗x<ai 即可将 ai 变成 ai⊗x ，拿去 ai−(ai⊗x) 个棋子.

统计满足 ai⊗x<ai 的个数.

代码

#include <cstdio>
#include <cctype>

const int N=;

int n;
int a[N];

inline int read(void)
{
    int x=; char c=getchar();
    for (;!isdigit(c);c=getchar());
    for (;isdigit(c);c=getchar()) x=x*+c-'0';
    return x;
}

int x;
int cnt;

int main(void)
{
    for (;;)
    {
        if (!(n=read())) break;
        for (int i=;i<=n;i++) a[i]=read();
        x=; for (int i=;i<=n;i++) x^=a[i];
        cnt=; for (int i=;i<=n;i++) cnt=cnt+((a[i]^x)<a[i]);
        printf("%d\n",cnt);
    }

    return ;
}