P13587 [NWRRC 2023] Game of Nim

Georgiy 和 Gennady 在学习了经典的 Nim 游戏后，发明了一个新游戏。这个游戏用 $n$ 个石子进行，分为两个阶段。 在准备阶段，Georgiy 选择一个正整数 $p < n$，并在游戏场上放置一堆 $p$ 个石子。 之后，Gennady 用剩下的 $(n - p)$ 个石子，任意分成若干堆，每堆的石子数也可以任意。 例如，如果 $n = 10$ 且 $p = 2$，Gennady 可以分成： - $8$ 堆，每堆 $1$ 个石子， - 或 $1$ 堆 $5$ 个石子和 $1$ 堆 $3$ 个石子， - 或 $2$ 堆 $2$ 个石子和 $4$ 堆 $1$ 个石子， - 或 $1$ 堆 $8$ 个石子， - 等等。 准备阶段结束后，进入 Nim 阶段。此时按照 Nim 游戏规则进行。两位玩家轮流操作，从 Georgiy 开始。每次操作，玩家必须从某一堆中取走至少一个石子，可以取任意多个，但只能从同一堆取。取走最后一个石子的玩家赢得 Nim 游戏，也就赢得整个游戏。 现在游戏刚开始，正处于准备阶段的中间：Georgiy 已经放好了 $p$ 个石子的一堆，但 Gennady 还没有把剩下的 $(n - p)$ 个石子分堆。现在 Gennady 想知道自己获胜的机会有多少。 请你计算，Gennady 有多少种方式将 $(n - p)$ 个石子分成若干堆，使得他能够赢得游戏（假设双方都会最优地进行 Nim 游戏）。 你可能知道，根据 Sprague-Grundy 理论，只有当所有堆的石子数（包括 $p$ 个石子的那一堆和 Gennady 分出的所有堆）的按位异或（XOR）结果为 $0$ 时，Gennady 才能获胜。 由于答案可能很大，请你输出答案对 $m$ 取模的结果。两种分法被认为不同，当且仅当对应的石子堆大小的多重集不同——也就是说，堆的顺序无关紧要。

一行，包含三个整数 $n$、$p$ 和 $m$，分别表示游戏中的石子总数、Georgiy 选择的那一堆的石子数，以及取模的值（$1 \le p < n \le 500$，$2 \le m \le 10^9$）。

输出一个整数，表示 Gennady 能够将剩下的 $(n - p)$ 个石子分堆并最终获胜的方案数，对 $m$ 取模。

在第一个样例中，Gennady 获胜的两种分法分别是： - 一堆 $3$ 个石子和两堆 $1$ 个石子， - 或一堆 $2$ 个石子和三堆 $1$ 个石子。 在第二个样例中，无论 Gennady 如何分配剩下的 $3$ 个石子，他都必输。 由 ChatGPT 4.1 翻译