C++算法
隔板法指南：从分球入盒到不定方程的组合计数解法
隔板法用于解决相同元素分配到不同盒子的问题。核心原理是将分配转化为插空组合问题。包含两个基础模型：每个盒子至少一个元素对应正整数解，盒子可为空对应非负整数解。通过借球法可转换模型。文章结合洛谷 P1771 真题，演示了利用快速幂计算指数取模及杨辉三角递推配合高精度加法求解大组合数的方法，并提供了空间优化版本代码。此外还涵盖元素有上限限制、多组分配等扩展场景，以及常见误区如混淆元素盒子属性、边界条件处理和高精度进位错误等避坑指南。
隔板法用于解决相同元素分配到不同盒子的问题。核心原理是将分配转化为插空组合问题。包含两个基础模型：每个盒子至少一个元素对应正整数解，盒子可为空对应非负整数解。通过借球法可转换模型。文章结合洛谷 P1771 真题，演示了利用快速幂计算指数取模及杨辉三角递推配合高精度加法求解大组合数的方法，并提供了空间优化版本代码。此外还涵盖元素有上限限制、多组分配等扩展场景，以及常见误区如混淆元素盒子属性、边界条件处理和高精度进位错误等避坑指南。
隔板法的核心思想是：将'相同元素的分配'转化为'在元素间隙中插入隔板'的组合问题。
举个直观的例子：有 6 个相同的小球，要分成 4 组（对应 4 个不同的盒子），每个组至少有 1 个小球。怎么分？
这个例子为大家诠释了隔板法的本质：相同元素的分配问题，等价于在元素间隙中选隔板的组合问题。
隔板法主要有两个核心模型，分别对应'每个盒子至少 1 个元素'和'盒子可以为空'两种情况，掌握这两个模型，就能解决 90% 以上的分配问题。
问题描述：有 n 个相同的元素，要分配到 k 个不同的盒子中，每个盒子至少放 1 个元素，求有多少种分配方案？
推导过程：
适用场景：
示例验证：
问题描述：有 n 个相同的元素，要分配到 k 个不同的盒子中，盒子可以为空（允许不放元素），求有多少种分配方案？
推导过程：
根据模型一，方案数为 C(n+k-1, k-1)。
适用场景：
示例验证：
为了方便大家快速区分和记忆两个模型，这里整理了核心对比表：
| 模型 | 条件限制 | 方案数公式 | 对应方程解 |
|---|---|---|---|
| 模型一 | 每个盒子至少 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=4。
无上限方案数（模型二）：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