ACM___________________________

MiYu原創(chuàng), 轉帖請注明 : 轉載自 ______________白白の屋

一.
      如果a1^a2^a3^...^an=0 ( 即 : nim-sum=0 ) , 說明先手沒有必贏策略, 方法數(shù)肯定為 0;
二.

      假設先手的人有必贏策略。

            問題則轉化為=>在任意一堆拿任意K張牌，并且剩下所有堆的nim-sum=0(P-position)的方案總數(shù)。

                     1. 現(xiàn)在我們先看一個例子(5,7,9)，并假設從第一堆取任意K張牌。

                              排除第一堆牌的nim-sum為 7^9=14

                                            0111

                                          ^1001

                                          -------

                                            1110

                              如果要使所有堆的nim-sum=0成立，則第一堆取掉K張以后必定為1110，因為X^X=0。

                              所以要觀察 5-k=14 k>0 成立,此例子(在第一堆取任意K張牌)明顯的不成立。但并不代表在第二或第三堆取任意K張牌的解不成立。

                     2. 現(xiàn)在看第二個例子(15,7,9)，并假設從第一堆取任意K張牌。

                              排隊第一堆牌的nim-sum為7^9=14，和第一個例子相同，所以問題變?yōu)橛^察 15-k=14 k>0 是否成立。

                              當然這個例子是成立的。

三.
      總結得出：

            在任意一堆拿任意K張牌，并且所有堆的nim-sum=0 成立的條件為：排除取掉K張牌的那一堆的nim-sum必須少于該堆牌上的數(shù)量(例子二)，否則不能在此堆上取任意K張牌使所有堆的nim-sum=0成立(例子一)。

            故總方案數(shù)為 ( 在任意一堆拿任意K張牌，并且所有堆的nim-sum=0 成立 ) 的總數(shù)。