「HDU1850&POJ2975」题解

题目1

题目2 ## 题意 Nim游戏的第一步有几种必胜走法

思路

考虑Nim游戏的模型 1. 结束状态是全为\(0\), 此时\(a_1\otimes a_2\otimes\dots\otimes a_n=0\) 2. \(a_1\otimes a_2\otimes\dots\otimes a_n=k\)时, 考虑\(k\)最高的二进制为\(1\)的一位, 一定有奇数个\(a_i\)满足该位为\(1\), 取其中的任意一个\(a_i\otimes k\), 该位会变成\(0\), 由于\(k\)的更高位为\(0\), 所以\(k\)的更高位不会改变, 因此\(a_i\otimes k<a_i\), 所以必定存在\(a_i\)使得\(a_1\otimes a_2\otimes\dots\otimes (a_i\otimes k)\otimes\dots\otimes a_n=0\)转移到必负状态 3. \(a_1\otimes a_2\otimes\dots\otimes a_n=0\)时, 对于任意\(a_i\)和\(k\in N^\*\)都有\(a_1\otimes a_2\otimes\dots\otimes (a_i\otimes k)\otimes\dots\otimes a_n=k\neq0\)转移到必胜状态

所以在初始状态, 只要把\(a_i\)变为\(a_i\otimes k(k=\bigotimes_{i=1}^n a_i)\)即可, 而初始状态可行方案的总数就是\(\sum_{i=1}^n[(a_i\otimes k) < a_i]\)

代码

const int N = 1005;

int a[N];

int main () {
  while (true) {
    int n;
    read(n);
    if (!n) {
      break;
    }
    int num = 0;
    for (int i = 1; i <= n; ++i) {
      read(a[i]);
      num ^= a[i];
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
      if ((num ^ a[i]) < a[i]) {
        ++ans;
      }
    }
    write(ans), EL;
  }
  return 0;
}