Step 1: 回顾 Nim 游戏结论。

  • Nim 游戏的必胜条件完全取决于所有堆石子数量的 异或和 。
  • 设 。
    • 若 ，先手必胜。
    • 若 ，先手必败。

Step 2: 分析小A的处境。

  • 小A 局面的异或和 。他有两种选择：
    1. 不作弊：此时 。
    2. 作弊：选择第 堆（要求 ），将其变为 。此时 。

Step 3: 分类讨论。

  • 情况 A：初始异或和 。已经是必胜态。
  • 情况 B：初始异或和 。如果不作弊，小A 必败。所以他必须作弊，试图让异或和变得不为 0。
    • 新的异或和 。只要 ，小A 就赢了。
    • 什么时候 呢？只要 ，即 ，那么异或和一定发生变化。前提条件是：必须存在至少一堆石子 ，让小A 有得拿。

结论：若 ，小A 必胜当且仅当 且 。否则必败 。

牛客写题解的编辑器好难用...