题解 P2197 【【模板】nim游戏】

· · 题解

博弈论的一道经典题,非常适合入门

由于nim游戏是公平组合游戏(ICG),所以当每一次操作后产生的新局面与操作前的局面无关,所以一个局面的必胜必负只受石子数影响

我们称将要进行操作的人为先手,另一人为后手

我们设第i堆的石子数为a_i

所以当a_1=a_2=...=a_n=0时,那时的先手就输了

我们先来引入一个新的知识异或运算(用xor表示),比如a~xor~b=c就是看二进制数a和b相对应的位置上的数字是否相同,如果相同则运算的到的数c的这一位为0,反之为1,可以自己举几个例子.

举个例子:5~xor~12=101~xor~1100=0101~xor~1100=1001=9 所以当a~xor~b~xor~c~xor~d~xor~e~xor~f=g(从左到右算,且支持交换律与结合律),如果g转化为二进制的第i位为1,说明a,b,c,d,e,f中有奇数个数第i位为1(奇数个1异或完还是1),反之有偶数个1(0也是偶数)

在c++中用符号"^"来表示这个操作,如5^12=9

所以当a_1=a_2=...=a_n=0时,a_1~xor~a_2~xor...a_n=0 (即他们的异或和为0)

所以当a_1~xor~a_2~xor...a_n≠0时,此时先手就一定还可以进行操作(我们设此时的先手为甲,后手为乙)

我们设此时a_1~xor~a_2~xor...a_n=k,我们假设k的最高位的1为的i位(如1001最高位为第4位),a_1 ~- ~a_n中有有奇数个数第i位为1,我们设a_j的第i位为1,因为a_j~xor ~k<a_j,因为xor~ k后得到的数与a_j相比第i位变为0,所以无论第1到i-1位怎么变,a_j~xor ~k肯定小于a_j(如10100~ xor~ 111= 10011,10011<10100),且a_j~xor~k≥0,所以我们可以取走a_j若干个石子使它只有a_j~xor~k个石子

此时原式变为a_1~xor~a_2~xor...xor~a_j~xor~k~xor~....xor~a_n=k~xor~(a_1~xor~a_2~xor...a_n)=k~xor~k=0,所以当a_1~xor~a_2~xor...a_n≠0时,先手可以取走一些石子使a_1~xor~a_2~xor...a_n=0,而之后乙无论怎么操作又会使a_1~xor~a_2~xor...a_n≠0(前面等于0时,a_1-a_n中第任意一位为1的数的个数都为偶,对其中一个数进行操作后一定会使某一些位为1的数的个数为奇)

所以之后甲为先手的局面都是a_1~xor~a_2~xor...a_n≠0,而乙都是a_1~xor~a_2~xor...a_n=0,总有一天,乙的局面会变为a_1=a_2=...=a_n=0(因为其中的数一直在减小),甲获胜

所以当a_1~xor~a_2~xor...a_n≠0时,此时先手必胜(可以像甲那样操作取得胜利)

反之当a_1~xor~a_2~xor...a_n=0时,此时先手必败(无论先手怎么操作都会使下一轮的变为a_1~xor~a_2~xor...a_n≠0,使下一轮的先手(这一轮的后手)必胜)

上代码

#include<bits/stdc++.h>
using namespace std;
int t,n,sum;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        sum=0;
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            sum^=x;
        }
        if(!sum) cout<<"No"<<'\n';//为0,必败
        else cout<<"Yes"<<'\n';//不为0,必胜
    }
    return 0;
}