题目分析

有一个长度为 $2n+1$ 的尺子，刻度编号为 $-n, -(n-1), \dots, -1, 0, 1, \dots, n$。初始时每个刻度上有一个橡皮，系统平衡（力矩和为0）。现在要拿走 $k$ 个橡皮，要求拿走后的系统仍然保持平衡。

我们需要计算满足条件的方案数，结果对 $p$ 取模。

问题转化

设拿走的 $k$ 个橡皮的位置为 $x_1, x_2, \dots, x_k$（每个 $x_i \in [-n, n]$），则平衡条件为：

通过坐标平移 $y_i = x_i + n$，问题转化为：

• 每个 $y_i \in [0, 2n]$
• $\sum_{i=1}^k y_i = nk$

解题思路

使用动态规划求解：

设 f[i][j] 表示用 $j$ 个在 $[0, 2n]$ 范围内的整数凑出和为 $i$ 的方案数。

递推关系基于整数划分的经典方法，并加入范围限制。

关键公式

递推公式：

f[i][j] = f[i-j][j] + f[i-j][j-1] - f[i-(n+1)*2][j-1]

其中：

• f[i-j][j]：所有数都 ≥ 1 的情况
• f[i-j][j-1]：包含0的情况
• 减去 f[i-(n+1)*2][j-1]：排除超出范围的情况

完整代码

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1e4 + 10;

int main() {
    int T;
    cin >> T;
    
    while (T--) {
        int n, k, PR;
        cin >> n >> k >> PR;
        
        // f[i][j]: 用j个在[0,2n]范围内的数凑出和为i的方案数
        int f[300000][20] = {0};
        f[0][0] = 1;
        
        for (int i = 1; i <= (n + 1) * k; i++) {
            for (int j = 1; j <= k && j <= i; j++) {
                // 基础递推
                f[i][j] = (f[i - j][j] + f[i - j][j - 1]) % PR;
                
                // 减去超出范围的情况
                if (i >= (n + 1) * 2) {
                    f[i][j] = (f[i][j] - f[i - (n + 1) * 2][j - 1]) % PR;
                }
            }
        }
        
        // 处理负数取模
        int result = (f[(n + 1) * k][k] + PR) % PR;
        cout << result << endl;
    }
    
    return 0;
}

代码说明

主要变量：

• n：尺子半长，总刻度数为 $2n+1$
• k：要拿走的橡皮数量
• PR：模数
• f[i][j]：动态规划数组

算法步骤：

1. 初始化 f[0][0] = 1
2. 遍历所有可能的和 i 和数量 j
3. 应用递推公式计算方案数
4. 处理负数取模，输出结果

关键点：

• 通过坐标平移将问题转化为非负整数划分
• 递推时及时减去超出范围的情况
• 最终答案为 f[(n+1)*k][k]，对应原问题中和为0的情况

复杂度分析

• 时间复杂度：$O(nk^2)$
  • 外层循环：$(n+1)k$ 次
  • 内层循环：最多 $k$ 次
• 空间复杂度：$O(nk)$