【算法基础篇】（五十三）隔板法指南：从 “分球入盒” 到不定方程，组合计数的万能解题模板

前言

在组合数学的世界里，有一类问题堪称 “高频刚需”—— 将相同元素进行分配。比如：把 10 个相同的苹果分给 3 个小朋友，每个小朋友至少分 1 个，有多少种分法？再比如：求解不定方程x1​+x2​+x3​=8的正整数解有多少组？ 这些看似毫无关联的问题，背后都隐藏着同一个解题神器 ——隔板法。它就像组合计数中的 “瑞士军刀”，能快速将复杂的分配问题转化为简单的组合数计算，让你在算法竞赛中秒解同类题目。 本文将从隔板法的核心原理入手，详细拆解两种基础模型、推导过程和适用场景，再通过洛谷经典真题（方程的解）实战演练，提供完整的 C++ 代码（含空间优化版本）和细节注释。无论你是算法新手，还是想巩固组合计数的进阶选手，跟着这篇文章学，就能彻底掌握隔板法的精髓！下面就让我们正式开始吧！

一、隔板法核心原理：把分配问题变成 “插空” 游戏

1.1 隔板法的本质

隔板法的核心思想是：将 “相同元素的分配” 转化为 “在元素间隙中插入隔板” 的组合问题。

举个直观的例子：有 6 个相同的小球，要分成 4 组（对应 4 个不同的盒子），每个组至少有 1 个小球。怎么分？

• 第一步：把 6 个小球排成一排，中间会产生 5 个空隙（比如：○ □ ○ □ ○ □ ○ □ ○ □ ○，其中□代表空隙）。
• 第二步：在这 5 个空隙中选 3 个插入隔板，就能把小球分成 4 组（比如：○○|○|○○|○，对应 2、1、2、1 个小球）。
• 第三步：总的分法数，就是从 5 个空隙中选 3 个的组合数，即C53​=10种。

这个例子为大家诠释了隔板法的本质：相同元素的分配问题，等价于在元素间隙中选隔板的组合问题。

1.2 两个基础模型：覆盖所有分配场景

隔板法主要有两个核心模型，分别对应 “每个盒子至少 1 个元素” 和 “盒子可以为空” 两种情况，掌握这两个模型，就能解决 90% 以上的分配问题。

模型一：每个盒子至少 1 个元素（正整数解）

问题描述：有 n 个相同的元素，要分配到 k 个不同的盒子中，每个盒子至少放 1 个元素，求有多少种分配方案？

推导过程：

• n 个相同元素排成一排，中间有n−1个空隙（因为两个元素之间一个空隙，n 个元素就是 n-1 个）。
• 要分成 k 组，需要插入k−1个隔板（比如 3 个盒子需要 2 个隔板）。
• 由于每个盒子至少 1 个元素，隔板不能插在同一个空隙（否则会有盒子为空），也不能插在两端（没有意义）。
• 因此，方案数就是从n−1个空隙中选k−1个的组合数，即：

​

适用场景：

• 相同元素分配，每个接收方至少 1 个（如分苹果、分糖果）。
• 不定方程

的正整数解组数（xi​≥1）。

示例验证：

• 问题：将 6 个相同小球分给 4 个盒子，每个盒子至少 1 个，方案数是多少？
• 解答：n=6，k=4，方案数

，和之前的例子一致。

模型二：盒子可以为空（非负整数解）

问题描述：有 n 个相同的元素，要分配到 k 个不同的盒子中，盒子可以为空（允许不放元素），求有多少种分配方案？

推导过程：

• 直接用模型一无法解决，因为模型一要求每个盒子至少 1 个元素。这里的关键技巧是 “借球法”—— 先给每个盒子 “借” 1 个元素，让每个盒子至少有 1 个元素，再用模型一求解。
• 具体步骤：
  1. 借球：给 k 个盒子各借 1 个元素，总共借了 k 个元素，此时元素总数变为n+k个。
  2. 分配：现在问题转化为 “将n+k个相同元素分给 k 个盒子，每个盒子至少 1 个元素”，符合模型一的条件。
  3. 还原：分配完成后，再从每个盒子中拿走 1 个 “借” 来的元素，就回到了 “n 个元素分给 k 个盒子，允许为空” 的原始问题。
• 根据模型一，方案数为

。

适用场景：

• 相同元素分配，允许部分接收方为空（如分配任务，部分人可以不分配）。
• 不定方程

的非负整数解组数（xi​≥0）。

示例验证：

• 问题：将 6 个相同小球分给 4 个盒子，盒子可以为空，方案数是多少？
• 解答：n=6，k=4，方案数为：

。

1.3 模型对比与记忆技巧

为了方便大家快速区分和记忆两个模型，这里整理了核心对比表：

记忆口诀：

• 至少一个：减一选减一（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)=xxmod1000（即xx除以 1000 的余数）。
• 要求方程的正整数解组数（每个ai​≥1）。

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

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

示例一：

输入：3 2

输出：3

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

2.2 题目分析

步骤 1：问题转化

• 首先计算

，得到 n = g (x)。

• 方程

的正整数解组数，正好对应隔板法的模型一（每个ai​≥1）。

• 根据模型一，解组数为

。

步骤 2：核心难点

1. 高精度计算：n = x^x mod 1000，x 可能很大，但 n 的范围是 0~999（因为 mod 1000）。k 的范围没有明确给出，但 n-1 最大为 998，k-1 最大为 998（若 k>n，则解组数为 0）。因此，组合数

可能很大（比如

是一个超级大的数），需要用高精度计算。

1. 避免除法：组合数的公式是

，但高精度除法实现复杂。这里可以用杨辉三角的递推公式

​，用加法递推避免除法，简化实现。

步骤 3：解题思路

1. 计算 n = x^x mod 1000（用快速幂实现，避免溢出）。
2. 若 n < k：方程无解，输出 0（因为正整数解要求每个 a_i≥1，k 个 a_i 之和至少为 k，若 n<k 则不可能）。
3. 否则，计算组合数

​：用杨辉三角递推 + 高精度存储结果。

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]，空间复杂度较高。由于递推公式

中，第 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 个”，方案数为

（若 n' < k，则方案数为 0）。

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

• 第一步：每个盒子先放 1 个，共放 3 个，剩下 10-3=7 个。
• 第二步：方案数

。

3.2 元素有上限限制

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

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

• 第一步：先计算无上限的方案数（模型二，允许为空）：

。

• 第二步：减去 “至少有一个盒子超过 t 个” 的方案数，加上 “至少有两个盒子超过 t 个” 的方案数，以此类推（容斥原理）。
• 具体公式：

，其中 max_i 是满足i∗(t+1)≤n的最大整数（超过则方案数为 0）。

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

• 无上限方案数（模型二）：

。

• 减去 “至少一个盒子超过 3 个” 的方案数：
  • 选 1 个盒子超过 3 个：

  

  ​。

  • 该盒子至少放 4 个，剩下 5-4=1 个元素分给 2 个盒子（允许为空）：

  

  。

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

3.3 多组分配问题

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

解法：组合数 + 隔板法。

• 第一步：将 n 个元素分成 m 组（每组至少 1 个）：

。

• 第二步：从 k 个盒子中选 m 个盒子分配这 m 组（每组对应一个盒子）：

。

• 总方案数：

。

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

• 第一步：分成 2 组：C6−12−1​=C51​=5种。
• 第二步：选 2 个盒子分配：A32​=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++ 代码。希望大家在学习后，能够多做练习，灵活运用隔板法，在算法竞赛中快速破解同类题目。 最后，记住隔板法的核心口诀：“相同元素分不同盒，隔板插空来相助；至少一个减一选，允许为空加一选”。相信只要勤加练习，你一定能把隔板法运用得炉火纯青！