自动搬运

查看原文

来自洛谷，原作者为

	NZSWW33OMF2GC **

搬运于2025-08-24 21:39:55，当前版本为作者最后更新于2020-03-26 23:30:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这题纯组合数学妥妥的做掉好吧！！下面用高中学过的一点小技巧过一遍。

这方法真的很简单而且说不定高考用得上

题解页面公式会挂掉，所以请移步此处。

---

问题重述

有两种球，分别是黑球（信号 0）和 红球（信号 1），相同类别的球之间没有区别。现在有 $n$ 个各不相同的盒子（储存区），要把 $a$ 个黑球和 $b$ 个红球放进这些盒子里。求方案总数。

每个盒子可以装任意多球，也可以不装。并且以上 $a+b$ 个球不需要全部放进盒子里，甚至可以不放任何球进盒子里。

---

问题分析

首先，既然不需要全部放进盒子里，那就讨论每一类球数确定时的情况。我们记 $n$ 个盒子，放 $i$ 个黑球以及 $j$ 个红球（全部放进去）的方案数为

$$f(n, i, j),\quad (0 \leq i \leq a,\ 0 \leq j \leq b). $$

显然（真的！），那么题中所求的总方案数就可以表达为

$$\mathrm{ans} = \sum_{i=0}^a \sum_{j=0}^b f(n, i, j), $$

（公式挂了的话到这里吧）

也就是一个二重循环的事情了。

那么现在我们需要知道这个 $f(n, i, j)$ 怎么算。这是放 $i$ 个黑球，再放 $j$ 个红球的方案数，这两步操作是独立的，也就是

$$f(n, i, j) = g(n, i) \cdot g(n, j),$$

其中 $g(n, k)$ 表示的是 $n$ 个盒子中放入 $k$ 个同类球的方案数。

（为什么放两种球相互独立呢？相信聪明的你一下就会明白的！）

那么我们就只需要知道如何将 $k$ 个球分给 $n$ 个盒子了。高二高三的同学肯定已经做过不少这样的题目了。这里用一种巧妙的隔板法来解决：

隔板法

我们先退一步。$k$ 个球分给 $n$ 个盒子。我们假设，题目要求变为每个盒子至少要分得一个球，如何解决呢？

$k$ 个球之间形成了 $k-1$ 个间隙，我们将 $n-1$ 个隔板插入间隙中，隔板就将球分为了 $k$ 份，符合假设。这样从 $k-1$ 个间隙中选出 $n-1$ 个插入隔板，即方案数为 $\mathrm{\large C}_{k-1}^{n-1}$.

但是现在要解决的情况是盒子可以分不到球。这样我们通过一步化归，转换为上面的情况：添加 $n$ 个球，使每个盒子至少有一个球。这样分完后只要将每个盒子多拿的一个球收回，便回到原情况了。于是得到方案数 $\mathrm{\large C}_{k+n-1}^{n-1}$.

（为什么不让每个间隙能插入多块隔板呢？仔细想想，这一步处理毫无意义。）

这个称为隔板法的方法经常可以应用到在高中的排列组合题目中。

---

这么一来，整个方案数的表达式已经确定了：

$$\begin{aligned} \mathrm{ans} &= \sum_{i=0}^a \sum_{j=0}^b f(n, i, j)\\ &= \sum _ {i=0}^a \sum_{j=0}^b g(n, i)\,g(n, j)\\ &= \sum _ {i=0}^a \sum_{j=0}^b \mathrm{\large C}_{i+n-1}^{n-1} \cdot \mathrm{\large C}_{j+n-1}^{n-1}. \end{aligned} $$

（公式挂了的话到这里吧）

先递推算出组合数存入数组，然后再计算上式即可。

核心代码：

for(int i = 0; i <= a; i++)
    for(int j = 0; j <= b; j++)
        ans += comb[n+i-1][n-1] * comb[n+j-1][n-1];

再来看一下数据范围。这里的组合数需要算到多大呢？容易看出最大总元素数（就是 $\mathrm{C}$ 的那个下标）是 $n+\max(a, b)-1$。根据题给范围，我们最多需要算到 $\mathrm{\large C}_{49}^{k}$. 可以验证，这不需要高精度，但是一定要开 unsigned long long！切记！ $\large\texttt{unsigned long long }!$

---

啊，写了两个小时。如果您看明白了的话，请给个赞吧 ^_^