HDU 4388 Stone Game II [博弈]

　　一堆N个石头，每人每回合可以将其分成K和N^K两堆，并且满足K<N且N^K<N，最后不能移动的人失败。

　　用F(N)代表N里面1的个数，容易推出F(N)和F(K)+F(N^K)的奇偶性相同。最后的终态是F(X)=1，即最后的堆数只和1的个数有关。所以如果F(N)=奇数，一定经过偶数次操作到达终态，如果F(N)是偶数，一定经过奇数次操作到达终态。

　　所以只要看1的个数为奇数的堆有多少个就知道输赢了。

 1 #include <string.h>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 using namespace std;
 5 int cas, n, k, ans;
 6 int bitcount(int x){
 7     int ret = 0;
 8     while(x) x = x&(x-1), ret++;
 9     return ret;
10 }
11 int main(){
12     scanf("%d", &cas);
13     for (int ca = 1; ca <= cas; ca++) {
14         scanf("%d", &n);
15         ans = 0;
16         while (n--) scanf("%d", &k), ans ^= (bitcount(k)%2==0);
17         printf("Case %d: %s\n", ca,ans ? "Yes" : "No");
18     }
19     return 0;
20 }