ニムゲームの実現

ニムゲームの思想は主に:3つのいくつかの品物があって、2人は交代である山から任意の多くの品物を取って、毎回少なくとも1つを取ることを規定して、多い者は限らないで、最後に光を取る者は勝つ.
この状況が最も興味深いのはバイナリと密接な関係があります私たちは(a,b,c)である情勢を表し、まず(0,0,0)は明らかに奇異な情勢であり、誰が奇異な情勢に直面しても必ず失敗する.第2の奇異な情勢は(0,n,n)であり、相手と同じように多くのものを持って行けば、最後に(0,0,0)を招く.よく分析してみると、(1,2,3)も奇異な情勢であり,相手がどう取っても次は(0,n,n)の状況になる.
計算機アルゴリズムには、ビット型2プラスと呼ばれる異或演算もあります.この演算を記号(+)で表し、まず(1,2,3)のビット型2プラスの結果を見てみましょう.
1=バイナリ01
2=バイナリ10
3=バイナリ11(+)
———————
0=バイナリ00(位置を上げないことに注意)
奇異な情勢(0,n,n)に対しても同様であり,結果も0であった.
いかなる奇異な情勢(a,b,c)にもa(+)b(+)c=0がある.
異和演算の交換則と結合則に注意し、a(+)a=0,:
a(+)b(+)(a(+)b)=(a(+)a)(+)(b(+)b)=0(+)0=0.
非奇異な情勢から奇異な情勢に転換する方法は、
1)a=c(+)b 2)b=a(+)c 3)c=a(+)b
分析:NP问题、必胜态N(next player wins)、必败态P(previous player wins)必胜态の场合、相手がどのように状态を必败态に调整しても、一定の処理で元の数を减らして必胜态に达することができ、必胜态の保持はゲームの胜利を促すので、ゲームの鍵は必胜态を夺うことができるかどうかにある.最後に品物を手に入れた人が勝つと仮定します.
必敗局面:奇異な情勢とも呼ばれる.どんな操作をしても、結局は負ける局面だ.必敗局面は2回の操作を経て、もう一つの必敗局面に達することができる.
必勝局面:1回の操作を経て必敗局面に達することができる.
すなわち、現在の局面は必敗局面ではなく必勝局面であり、必勝局面は一歩で必敗局面に転換することができる.
最終状態:(1)最後に品物が山積みになる;(必勝局面)
(2)残り2つ、1つずつ;(必敗局面)
(3)品物が2つ残っていて、そのうちの1つが1つしか残っていない場合、もう1つがnつ以上残っている場合、現在取っている人は1つ以上のものをn-1つ取り出すだけで、さっき述べた必敗局面になります.(必勝局面)
次は勝つかどうかを判断する鍵である.すなわち、奇異な情勢にあるかどうかを判断する.1)各グループのすべての数字をバイナリ数で表し、異或を行い、異或の結果がゼロであれば必敗であり、逆にゼロでなければ必勝である.2)必勝の場合,すべての数がゼロより大きいため,最大ビット数と空席が異なるか、ゼロより大きい最大ビット数が得られるに違いない.(例えば、2つの品物の山で、異種を除去した後のバイナリを10と表すと、その中の大きいものは必ず2桁で、2つの数は111または100)で、必勝を必敗に変えるには、大きな数を一定数取り、最高位を同じにし、その後の数も一定の条件を備え、異種を取得した後の値をゼロにする必要があります.
解析により,以上の推定から既知のスタック当たりの数とスタック数に基づいて状況を推定し,コード実装することができる.

C:
#include 
using namespace std;
int main(){
    int m,ans,n;
    while(~scanf("%d",&m)){
        n=ans=0;
        while(m--)
            scanf("%d",&n),ans^=n,printf("ans=%d
",ans);
        if(ans)printf("Yes
");
        else printf("No
");
    }
}