组合杂题

练习题

ARC110D - Binomial Coefficient is Fun (opens new window)

提示

显然只有$B_i\geq A_i$才有意义，这时，将$B_i\choose A_i$看成是从$B_i$个球中选$A_i$个进行染色。

现在，对于某一种染色方案（也即我们计数的基本单元），我们染色后的$B_1,B_2,\dots,B_n$个球一字排开。考虑到$A_i$有可能为$0$，我们在第$i$组的最后再额外放上一个染色的球，以表示组与组之间的分隔。因为$\sum B_i\leq M$，对于$\sum B_i<N+M$的情形，我们不妨在最后补上$N+M-\sum B_i$个球，这些球显然是没有染色的。

这样，对于每一种染色方案，我们都可以得到唯一确定的一个排列，而这个排列可以看成是在$N+M$个球（包括$N$个添加在每组末尾用于分隔的球）中选取$N+\sum A_i$个进行染色后得到的。

现在，反过来考虑。假设我们已经有了对$N+M$个球中选取$N+\sum A_i$个进行染色后得到的一个排列。我们可以从最后一个染色的球开始，首先确定第$N$组的范围，然后依次确定第$N-1,N-2,\dots,1$组的范围。从而，我们可以由这样一个排列得到唯一确定的一组$\{B_i\}$的取值。显然，这一排列对应于这一组$\{B_i\}$取值下的唯一确定的一种染色方案。

从而，我们说明了分组进行染色和对整体进行染色之间的一一映射关系，因此，这两种染色方法的方案总数应当是相等的。

所以，本题最后的答案就是${N+M}\choose{N+\sum A_i}$。