题解

思路

核心计数

设前 $i-1$ 种颜色共有

$$S_{i-1}=\sum_{j=1}^{i-1}c_j$$

颗球，并且它们已经排成满足要求的序列。加入颜色 $i$ 时，颜色 $i$ 的最后一颗球必须出现在此前所有颜色的最后一颗球之后，因此它必须放在新序列的末尾。

剩余 $c_i-1$ 颗颜色 $i$ 的球可以插入末尾之前的 $S_{i-1}+c_i-1$ 个位置。只需选择其中哪些位置放颜色 $i$，方案数为

$$\binom{S_{i-1}+c_i-1}{c_i-1}.$$

于是答案为

$$\prod_{i=2}^{k}\binom{S_{i-1}+c_i-1}{c_i-1}\pmod {10^9+7}.$$

做法

子任务 1

当 $k=2$ 时，只需计算

$$\binom{c_1+c_2-1}{c_2-1}.$$

也可以把它理解为从 $(0,0)$ 走到 $(c_1,c_2-1)$ 的网格路径数：每一步取出一颗颜色 $1$ 或一颗非末尾的颜色 $2$。使用滚动数组做二维递推，时间复杂度为 $O(c_1c_2)$，空间复杂度为 $O(c_2)$。

满分做法

模数 $P=10^9+7$ 是质数，且所有球的总数不超过 $1000<P$。预处理阶乘与逆阶乘：

$$\binom{n}{m}=n!\,(m!)^{-1}\,((n-m)!)^{-1}\pmod P.$$

逆元由费马小定理 $x^{-1}\equiv x^{P-2}\pmod P$ 求得。随后按颜色编号从小到大维护前缀球数并乘上上述组合数。

正确性证明

引理 1

固定一个满足前 $i-1$ 种颜色限制的序列。加入颜色 $i$ 后，新序列满足颜色 $i-1$ 的最后出现位置早于颜色 $i$ 的最后出现位置，当且仅当颜色 $i$ 的最后一颗球位于新序列末尾。

证明。 已有序列的末尾不晚于其中任意旧颜色的最后出现位置。若新序列末尾是颜色 $i$，则颜色 $i$ 的最后出现位置晚于所有旧颜色；反之，若末尾是旧颜色，则该旧颜色的最后出现位置晚于颜色 $i$，不满足要求。∎

引理 2

对固定的旧序列，合法加入颜色 $i$ 的方案数为 $\binom{S_{i-1}+c_i-1}{c_i-1}$。

证明。 由引理 1 固定末尾的一颗颜色 $i$ 后，其余位置共 $S_{i-1}+c_i-1$ 个。从中选择 $c_i-1$ 个位置放置不可区分的颜色 $i$ 球，其余位置保持旧序列的相对顺序。选择与所得新序列一一对应。∎

定理

算法输出所有合法取球序列的数量。

证明。 初始只有颜色 $1$ 时方案数为 $1$。依次加入颜色 $2,3,\ldots,k$，由引理 2，每个已有合法序列都恰好产生相同数量且互不重复的新合法序列，因此按乘法原理得到给定乘积。归纳可知最终恰好计数全部合法序列。∎

复杂度

预处理和逐色计算的时间复杂度为 $O(\sum c_i+k+\log P)$，空间复杂度为 $O(\sum c_i)$。