隔板法指南：从分球入盒到不定方程的组合计数解法

记忆口诀：

• 至少一个：减一选减一（n-1 选 k-1）。
• 可以为空：加一选减一（n+k-1 选 k-1）。

1.4 关键注意事项

1. 元素必须相同：隔板法的前提是元素相同，若元素不同（如分配不同的礼物），则不能用隔板法，需用排列数或乘法原理。
2. 盒子必须不同：盒子不同意味着'分给 A 盒子 2 个、B 盒子 1 个'和'分给 A 盒子 1 个、B 盒子 2 个'是不同方案。若盒子相同（如分成几组，不区分顺序），则需要额外去重。
3. 边界条件处理：
   • 当 n < k 且模型一（每个盒子至少 1 个）：方案数为 0（比如 3 个小球分给 5 个盒子，每个至少 1 个，不可能）。
   • 当 n=0（没有元素可分）且模型二（允许为空）：方案数为 1（只有'所有盒子都为空'一种情况）。

真题实战：洛谷 P1771 方程的解（隔板法 + 高精度）

题目链接：https://www.luogu.com.cn/problem/P1771

2.1 题目描述

佳佳碰到了一个难题，需要解决不定方程 a1+a2+...+ak=g(x)，其中：

• k≥2 且 k 是正整数。
• x 是正整数，g(x)=x^x mod 1000（即 x^x 除以 1000 的余数）。
• 要求方程的正整数解组数（每个 ai≥1）。

输入：一行两个正整数 k 和 x。

输出：方程的正整数解组数。

示例一：

输入：3 2

输出：3

解释：g(2)=2^2=4 mod 1000=4，方程变为 a1+a2+a3=4，正整数解有 3 组：(1,1,2)、(1,2,1)、(2,1,1)。

2.2 题目分析

步骤 1：问题转化

根据模型一，解组数为 C(n-1, k-1)。

方程 a1+a2+...+ak=n 的正整数解组数，正好对应隔板法的模型一（每个 ai≥1）。

首先计算 n = g(x)，得到 n = g(x)。

步骤 2：核心难点

避免除法：组合数的公式是 C(n,k) = n! / (k!(n-k)!)，但高精度除法实现复杂。这里可以用杨辉三角的递推公式 C(i,j) = C(i-1,j) + C(i-1,j-1)，用加法递推避免除法，简化实现。

高精度计算：n = x^x mod 1000，x 可能很大，但 n 的范围是 0~999（因为 mod 1000）。k 的范围没有明确给出，但 n-1 最大为 998，k-1 最大为 998（若 k>n，则解组数为 0）。因此，组合数 C(n-1, k-1) 可能很大（比如 C(998, 499) 是一个超级大的数），需要用高精度计算。

步骤 3：解题思路

1. 计算 n = x^x mod 1000（用快速幂实现，避免溢出）。
2. 若 n < k：方程无解，输出 0（因为正整数解要求每个 ai≥1，k 个 ai 之和至少为 k，若 n<k 则不可能）。
3. 否则，计算组合数 C(n-1, k-1)：用杨辉三角递推 + 高精度存储结果。

2.3 C++ 代码实现（完整版）

#include <iostream>
using namespace std;
typedef long long LL;
// 常量定义：
// N：n 的最大可能值（x^x mod 1000 ≤ 999，所以 n-1 ≤ 998）
// M：k 的最大可能值（k-1 ≤ n-1 ≤ 998）
// K：高精度数组的位数（足够存储 C(998,499)，约 1e300，所以 150 位足够）
const int N = 1010, M = 110, K = 150;
int k, x, n;
// f[i][j][k]：高精度存储 C(i,j)，第三维是数字的每一位（逆序存储，方便进位）
int f[N][M][K];

// 快速幂：计算 a^b mod p，用于计算 x^x mod 1000
LL qpow(LL a, LL b, LL p) {
    a %= p; // 先取模，避免溢出
    LL ret = 1;
    while (b) {
        if (b & 1) ret = ret * a % p; // 若 b 为奇数，乘上当前 a
        a = a * a % p; // a 平方
        b >>= 1; // b 右移一位（等价于 b//2）
    }
    return ret;
}

// 高精度加法：c = a + b（a 和 b 是逆序存储的高精度数组）
void add(int c[], int a[], int b[]) {
    for (int i = 0; i < K - 1; ++i) {
        c[i] += a[i] + b[i]; // 对应位相加
        c[i + 1] += c[i] / 10; // 进位
        c[i] %= 10; // 保留当前位
    }
}

int main() {
    cin >> k >> x;
    // 步骤 1：计算 n = x^x mod 1000
    n = qpow(x, x, 1000);
    // 步骤 2：判断是否有解（n >= k 才可能有正整数解）
    if (n < k) {
        cout << 0 << endl;
        return 0;
    }
    // 步骤 3：用杨辉三角递推计算 C(n-1, k-1)
    // 杨辉三角边界：C(i, 0) = 1（所有 i）
    for (int i = 0; i < n; ++i) {
        f[i][0][0] = 1; // C(i,0) = 1，逆序存储，第 0 位是个位 1
    }
    // 递推公式：C(i,j) = C(i-1,j) + C(i-1,j-1)
    for (int i = 1; i < n; ++i) {
        // j 的范围：1 <= j <= min(i, k-1)（因为我们只需要计算到 C(n-1, k-1)）
        for (int j = 1; j <= min(i, k-1); ++j) {
            add(f[i][j], f[i-1][j], f[i-1][j-1]);
        }
    }
    // 步骤 4：输出结果（f[n-1][k-1] 是逆序存储，需要倒序输出）
    int p = K - 1; // 找到最高位（跳过前面的 0）
    while (p >= 0 && f[n-1][k-1][p] == 0) --p;
    // 倒序输出每一位
    while (p >= 0) cout << f[n-1][k-1][p--];
    cout << endl;
    return 0;
}

2.4 代码优化：空间优化版本

上面的代码用了三维数组 f[N][M][K]，空间复杂度较高。由于递推公式 C(i,j) = C(i-1,j) + C(i-1,j-1) 中，第 i 层只依赖第 i-1 层的数据，因此可以优化为二维数组，减少空间占用。

空间优化版代码：

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1010, M = 110, K = 150;
int k, x, n;
// 优化为二维数组：f[j][k] 存储当前层的 C(i,j)
int f[M][K];

LL qpow(LL a, LL b, LL p) {
    a %= p;
    LL ret = 1;
    while (b) {
        if (b & 1) ret = ret * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ret;
}

// 高精度加法：c += b（因为优化后，a 就是 c 的上一轮值）
void add(int c[], int b[]) {
    for (int i = 0; i < K - 1; ++i) {
        c[i] += b[i];
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
}

int main() {
    cin >> k >> x;
    n = qpow(x, x, 1000);
    if (n < k) {
        cout << 0 << endl;
        return 0;
    }
    // 初始化：C(0,0) = 1
    f[0][0] = 1;
    // 递推：i 从 1 到 n-1（因为要计算 C(n-1, k-1)）
    for (int i = 1; i < n; ++i) {
        // 注意：j 要从 min(i, k-1) 倒序遍历，避免覆盖上一轮的 f[j-1]
        for (int j = min(i, k-1); j >= 1; --j) {
            add(f[j], f[j-1]);
        }
    }
    // 输出结果
    int p = K - 1;
    while (p >= 0 && f[k-1][p] == 0) --p;
    while (p >= 0) cout << f[k-1][p--];
    cout << endl;
    return 0;
}

2.5 代码细节解析

1. 快速幂计算 x^x mod 1000

由于 x 可能很大（比如 x=1e9），直接计算 x^x 会溢出，因此用快速幂高效计算，同时每一步取模 1000，保证结果在 int 范围内。快速幂的时间复杂度是 O(log x)，即使 x=1e18，log2(x) 也只有 60，效率极高。

2. 高精度存储与加法

高精度数组采用逆序存储（第 0 位是个位，第 1 位是十位，以此类推），这样进位时只需要向后（高位）累加，非常方便。加法函数 add 实现两个高精度数组的相加，处理进位时，当前位除以 10 的商是进位，余数是当前位的值。

3. 杨辉三角递推优化

空间优化的关键是倒序遍历 j：如果正序遍历 j，计算 f[j] 时，f[j-1] 已经被当前轮次的结果覆盖（因为 f[j-1] 在 j 之前更新），导致递推错误。倒序遍历可以保证 f[j-1] 是上一轮次的结果，正确参与计算。

4. 结果输出

高精度数组逆序存储，因此输出时需要从最高位（最后一个非零位）倒序输出，跳过前面的零。

2.6 测试用例验证

示例一输入：3 2

• 计算 n = 2^2 mod 1000 = 4。
• 需计算 C(4-1, 3-1) = C(3,2) = 3。
• 代码输出 3，与示例一致。

测试用例二：输入：2 5

• 计算 n = 5^5 mod 1000 = 3125 mod 1000 = 125。
• 需计算 C(125-1, 2-1) = C(124,1) = 124。
• 代码输出 124，正确。

测试用例三：输入：5 3

• 计算 n = 3^3 mod 1000 = 27。
• 需计算 C(27-1,5-1) = C(26,4) = 14950。
• 代码输出 14950，正确。

隔板法的扩展应用：从基础模型到复杂场景

隔板法的基础模型看似简单，但通过灵活变形，可以解决很多复杂的组合计数问题。以下是几个常见的扩展场景：

3.1 每个盒子至少 m 个元素

问题描述：有 n 个相同元素，分给 k 个不同盒子，每个盒子至少 m 个元素（m≥2），求方案数。

解法：转化为模型一（每个盒子至少 1 个）。

• 第一步：每个盒子先放 m-1 个元素，总共放了 k*(m-1) 个元素。
• 第二步：剩下的元素数为 n' = n - k*(m-1)。
• 第三步：问题转化为'将 n' 个元素分给 k 个盒子，每个盒子至少 1 个'，方案数为 C(n'-1, k-1)（若 n' < k，则方案数为 0）。

示例：将 10 个相同小球分给 3 个盒子，每个盒子至少 2 个，方案数是多少？

• 第一步：每个盒子先放 1 个，共放 3 个，剩下 10-3=7 个。
• 第二步：方案数 C(6,2)=15。

3.2 元素有上限限制

问题描述：有 n 个相同元素，分给 k 个不同盒子，每个盒子最多放 t 个元素，求方案数。

解法：正难则反 + 容斥原理 + 隔板法。

• 第一步：先计算无上限的方案数（模型二，允许为空）：C(n+k-1, k-1)。
• 第二步：减去'至少有一个盒子超过 t 个'的方案数，加上'至少有两个盒子超过 t 个'的方案数，以此类推（容斥原理）。

具体公式：

∑(-1)^i * C(k, i) * C(n - i*(t+1) + k - 1, k - 1)，其中 max_i 是满足 i*(t+1)≤n 的最大整数（超过则方案数为 0）。

示例：将 5 个相同小球分给 2 个盒子，每个盒子最多放 3 个，方案数是多少？

• 减去'至少一个盒子超过 3 个'的方案数：
  • 这部分方案数：2×2=4。
• 加上'至少两个盒子超过 3 个'的方案数：5 < 2*(3+1)=8，方案数为 0。
• 最终方案数：6-4=2 种（对应 (2,3)、(3,2)）。

该盒子至少放 4 个，剩下 5-4=1 个元素分给 2 个盒子（允许为空）：C(1+2-1, 2-1)=2。

选 1 个盒子超过 3 个：C(2,1)*2=4。

无上限方案数（模型二）：C(5+2-1, 2-1)=6。

3.3 多组分配问题

问题描述：有 n 个相同元素，分成 m 组，每组至少 1 个元素，再将这 m 组分配给 k 个不同盒子（k≥m），每个盒子最多分 1 组，求方案数。

解法：组合数 + 隔板法。

• 总方案数：C(n-1, m-1) * C(k, m) * m!
• 第一步：将 n 个元素分成 m 组（每组至少 1 个）：C(n-1, m-1)。
• 第二步：从 k 个盒子中选 m 个盒子分配这 m 组（每组对应一个盒子）：P(k, m)。

示例：将 6 个相同小球分成 2 组（每组至少 1 个），再分配给 3 个不同盒子（每个盒子最多 1 组），方案数是多少？

• 第一步：分成 2 组：C(6-1, 2-1)=C(5,1)=5 种。
• 第二步：选 2 个盒子分配：A(3,2)=3×2=6 种。
• 总方案数：5×6=30 种。

常见误区与避坑指南

4.1 混淆元素/盒子的'相同'与'不同'

• 错误场景：将不同元素用隔板法分配（如'3 本不同的书分给 2 个小朋友'）。
• 正确做法：不同元素分配用乘法原理（每个书有 2 种选择，方案数 2^3=8 种）。

4.2 忽略边界条件

• 错误场景：n=0 时，认为方案数为 0。
• 正确做法：n=0 且允许为空（模型二），方案数为 1（所有盒子都为空）；n=0 且要求每个盒子至少 1 个（模型一），方案数为 0。

4.3 高精度计算时的进位错误

• 错误场景：高精度数组正序存储，导致进位处理复杂，容易出错。
• 正确做法：采用逆序存储，进位时直接向后累加，简洁高效。

4.4 递推时的顺序错误（空间优化版）

• 错误场景：正序遍历 j，导致覆盖上一轮的 f[j-1]。
• 正确做法：倒序遍历 j，保证 f[j-1] 是上一轮的结果，递推正确。

总结

隔板法是组合计数中最实用的解题方法之一，核心是将'相同元素的分配问题'转化为'插隔板的组合问题'。掌握两个基础模型（每个盒子至少 1 个、允许为空），就能解决大多数基础题；通过'转化法''正难则反''容斥原理'等技巧，还能应对复杂的扩展场景。

本文通过洛谷真题 P1771，详细演示了隔板法的实际应用，同时解决了高精度计算、空间优化等关键问题，提供了可直接运行的 C++ 代码。建议在学习后多做练习，灵活运用隔板法，在算法竞赛中快速破解同类题目。

记住隔板法的核心口诀：'相同元素分不同盒，隔板插空来相助；至少一个减一选，允许为空加一选'。