C++算法
隔板法指南：从分球入盒到不定方程，组合计数解题模板
隔板法是解决相同元素分配问题的组合计数方法，核心是将分配转化为插空组合。文章详解两个基础模型：每个盒子至少一个元素对应正整数解，盒子可为空对应非负整数解。通过洛谷 P1771 真题实战，演示了如何利用隔板法求解不定方程，并结合快速幂与高精度计算处理大数问题。提供完整 C++ 代码及空间优化版本，解析杨辉三角递推、逆序存储进位等细节，帮助读者掌握算法竞赛中此类题目的通用解题模板。
隔板法是解决相同元素分配问题的组合计数方法，核心是将分配转化为插空组合。文章详解两个基础模型：每个盒子至少一个元素对应正整数解，盒子可为空对应非负整数解。通过洛谷 P1771 真题实战，演示了如何利用隔板法求解不定方程，并结合快速幂与高精度计算处理大数问题。提供完整 C++ 代码及空间优化版本，解析杨辉三角递推、逆序存储进位等细节，帮助读者掌握算法竞赛中此类题目的通用解题模板。
隔板法的核心思想是：将'相同元素的分配'转化为'在元素间隙中插入隔板'的组合问题。
举个直观的例子：有 6 个相同的小球，要分成 4 组（对应 4 个不同的盒子），每个组至少有 1 个小球。怎么分？
这个例子为大家诠释了隔板法的本质：相同元素的分配问题，等价于在元素间隙中选隔板的组合问题。
隔板法主要有两个核心模型，分别对应'每个盒子至少 1 个元素'和'盒子可以为空'两种情况，掌握这两个模型，就能解决 90% 以上的分配问题。
问题描述：有 n 个相同的元素，要分配到 k 个不同的盒子中，每个盒子至少放 1 个元素，求有多少种分配方案？
推导过程：
适用场景：
示例验证：
解答：n=6，k=4，方案数 C(5,3)=10，和之前的例子一致。
问题描述：有 n 个相同的元素，要分配到 k 个不同的盒子中，盒子可以为空（允许不放元素），求有多少种分配方案？
推导过程：
根据模型一，方案数为 C(n+k-1, k-1)。
适用场景：
示例验证：
解答：n=6，k=4，方案数为 C(9,3)=84。
为了方便大家快速区分和记忆两个模型，这里整理了核心对比表：
| 模型 | 条件限制 | 方案数公式 | 对应方程解 |
|---|---|---|---|
| 模型一 | 每个盒子至少 1 个元素 | C(n-1, k-1) | 正整数解（xi≥1） |
| 模型二 | 盒子可以为空 | C(n+k-1, k-1) | 非负整数解（xi≥0） |
记忆口诀：
题目链接：https://www.luogu.com.cn/problem/P1771
佳佳碰到了一个难题，需要解决不定方程 a1+a2+...+ak=g(x)，其中：
输入：一行两个正整数 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)。
根据模型一，解组数为 C(n-1, k-1)。
方程 a1+a2+...+ak=n 的正整数解组数，正好对应隔板法的模型一（每个 ai≥1）。
首先计算 n = g(x)，得到 n = g(x)。
避免除法：组合数的公式是 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) 是一个超级大的数），需要用高精度计算。
#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;
}
}
{
cin >> k >> x;
n = (x, x, );
(n < k) {
cout << << endl;
;
}
( i = ; i < n; ++i) {
f[i][][] = ;
}
( i = ; i < n; ++i) {
( j = ; j <= (i, k); ++j) {
(f[i][j], f[i][j], f[i][j]);
}
}
p = K - ;
(p >= && f[n][k][p] == ) --p;
(p >= ) cout << f[n][k][p--];
cout << endl;
;
}
上面的代码用了三维数组 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)）
( i = ; i < n; ++i) {
( j = (i, k); j >= ; --j) {
(f[j], f[j]);
}
}
p = K - ;
(p >= && f[k][p] == ) --p;
(p >= ) cout << f[k][p--];
cout << endl;
;
}
由于 x 可能很大（比如 x=1e9），直接计算 x^x 会溢出，因此用快速幂高效计算，同时每一步取模 1000，保证结果在 int 范围内。快速幂的时间复杂度是 O(log x)，即使 x=1e18，log2(x) 也只有 60，效率极高。
高精度数组采用逆序存储（第 0 位是个位，第 1 位是十位，以此类推），这样进位时只需要向后（高位）累加，非常方便。加法函数
add实现两个高精度数组的相加，处理进位时，当前位除以 10 的商是进位，余数是当前位的值。
空间优化的关键是倒序遍历 j：如果正序遍历 j，计算 f[j] 时，f[j-1] 已经被当前轮次的结果覆盖（因为 f[j-1] 在 j 之前更新），导致递推错误。倒序遍历可以保证 f[j-1] 是上一轮次的结果，正确参与计算。
高精度数组逆序存储，因此输出时需要从最高位（最后一个非零位）倒序输出，跳过前面的零。
示例一输入：3 2
测试用例二：输入：2 5
测试用例三：输入：5 3
隔板法的基础模型看似简单，但通过灵活变形，可以解决很多复杂的组合计数问题。以下是几个常见的扩展场景：
问题描述：有 n 个相同元素，分给 k 个不同盒子，每个盒子至少 m 个元素（m≥2），求方案数。
解法：转化为模型一（每个盒子至少 1 个）。
示例：将 10 个相同小球分给 3 个盒子，每个盒子至少 2 个，方案数是多少？
问题描述：有 n 个相同元素，分给 k 个不同盒子，每个盒子最多放 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 个，方案数是多少？
该盒子至少放 4 个，剩下 5-4=1 个元素分给 2 个盒子（允许为空）：C(1+2-1, 2-1)=2。 选 1 个盒子超过 3 个：C(2,1)=2。 无上限方案数（模型二）：C(5+2-1, 2-1)=6。
问题描述：有 n 个相同元素，分成 m 组，每组至少 1 个元素，再将这 m 组分配给 k 个不同盒子（k≥m），每个盒子最多分 1 组，求方案数。
解法：组合数 + 隔板法。
示例：将 6 个相同小球分成 2 组（每组至少 1 个），再分配给 3 个不同盒子（每个盒子最多 1 组），方案数是多少？
隔板法是组合计数中最实用的解题方法之一，核心是将'相同元素的分配问题'转化为'插隔板的组合问题'。掌握两个基础模型（每个盒子至少 1 个、允许为空），就能解决大多数基础题；通过'转化法''正难则反''容斥原理'等技巧，还能应对复杂的扩展场景。
本文通过洛谷真题 P1771，详细演示了隔板法的实际应用，同时解决了高精度计算、空间优化等关键问题，提供了可直接运行的 C++ 代码。希望大家在学习后，能够多做练习，灵活运用隔板法，在算法竞赛中快速破解同类题目。
最后，记住隔板法的核心口诀：'相同元素分不同盒，隔板插空来相助；至少一个减一选，允许为空加一选'。相信只要勤加练习，你一定能把隔板法运用得炉火纯青！
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online