题解：P13587 [NWRRC 2023] Game of Nim

Mysterious__Bird · 2025-12-01 23:04:13 · 题解

题意

经典的 NIM 游戏，由于题中已经给出 NIM 游戏的解法这里不过多赘述。我们要做的就是求出让各个堆的石子数异或和为 0 的方案数量。

思路

声明：在下文中 \otimes 表示异或。

我们可以很容易得到一个数按位异或他自己等于 0，即 x \otimes x=0。所以我们只需求将 n-p 个石子分为若干堆，使这若干堆石子数量异或和为 p。那么，我们该如何分这 n-p 个石子呢？

我们可以将问题分为两步解决。

第一步

考虑将一个正整数 n-p 分成若干个正整数的和有几种分法。不考虑顺序，如 3=1+2，3=2+1 视为同一种。这是一道很经典的背包问题。定义 f[i][j] 表示在仅考虑 1 \sim i 这些数的情况下使这些数的合为 j 的方案数。状态转移方程为：

我们要求的答案就是：f[n-p][n-p]。

第二步

考虑在第一步分完的情况下所有堆的石子数的异或和为 k 。我们神奇地发现，只需要在 f[i][j] 的基础上加上一个维度 k 即可定义 f[i][j][k] 表示在仅考虑 1 \sim i 这些数的情况下，使这些数的和为 j 且这些数的异或和为 k 的方案数。根据上一步我们可以很轻松地写出状态转移方程：

我们还可以利用滚动数组进行优化，让 j 从 i 开始遍历。于是我们得到了最终的状态转移方程：

我们要求的答案就是：f[n-p][p]。

当然，别忘了对每次的计算结果取模，最后附上 AC 代码。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 512;
int dp[N][N];

int main(){
    int n, p, m;
    cin >> n >> p >> m;
    int x = n-p;
    dp[0][0] = 1;
    for(int i=1;i<=x;i++){
        for(int j=i;j<=x;j++){
            for(int k=0;k<N;k++){
                dp[j][k] = (dp[j][k] + dp[j-i][k^i]) % m;
            }
        }
    }
    cout << dp[x][p];
    return 0;
}