P2638 【安全系统】题解
NZSWW33OMF2GC
·
·
题解
这题纯组合数学妥妥的做掉好吧！！下面用高中学过的一点小技巧过一遍。
这方法真的很简单而且说不定高考用得上
题解页面公式会挂掉，所以请移步此处。
问题重述
有两种球，分别是黑球（信号 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 个盒子。我们假设，题目要求变为每个盒子至少要分得一个球，如何解决呢？
但是现在要解决的情况是盒子可以分不到球。这样我们通过一步化归，转换为上面的情况：添加 $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}
$$
（公式挂了的话到[这里](https://www.luogu.com.cn/blog/x4Cx58x54/solution-p2638)吧）
先递推算出组合数存入数组，然后再计算上式即可。
核心代码：
```c++
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 }!
啊，写了两个小时。如果您看明白了的话，请给个赞吧 ^_^