题解

思路

先把每一个非 1 号球与一个 1 号球配成一对，并让这一对最终进入同一个箱子。

做法

设配对后剩余的 1 号球数为 $b=a_1-\sum_{i=2}^{N}a_i$。每个箱子还必须至少得到一个未配对的 1 号球，因此这些球的分配数为正整数拆分数 $\binom{b-1}{K-1}$；若 $b<K$，答案为零。

对每一种 $i>1$，它的 $a_i$ 个配对可以任意分到 $K$ 个有编号箱子，隔板法给出 $\binom{a_i+K-1}{K-1}$ 种。各球号相互独立，答案就是 $\binom{b-1}{K-1}\prod_{i=2}^{N}\binom{a_i+K-1}{K-1}$。组合数的下参数至多 $199$，直接连乘分子并乘预处理阶乘逆元即可；即使上参数跨过模数，连乘中出现零也会自然得到正确结果。

复杂度

时间复杂度为 $O(NK)$，额外空间复杂度为 $O(K)$。