题解 CF553A/554C - Kyoya and Colored Balls
Milmon
2022-06-14 10:03:48
[in Blog](//milk-lemon.blog.luogu.org/solution-CF553A) & [Problem](//www.luogu.com.cn/problem/CF553A)
## 题目大意
- 有 $n$ 个球，这些球有 $k$ 种颜色，颜色 $i$ 的球有 $c_i$ 个。
- 将这些球排序，满足 $\forall\ 1\leq i<n$，序列中最后一个颜色 $i$ 的球出现在序列中最后一个颜色 $i+1$ 的球之前。求合法的排序数量。
- $1\leq n,\ k,\ c_i\leq 10^3$
## 解题思路
考虑依次往序列中插入颜色为 $1$ 的球，颜色为 $2$ 的球，以此类推直到颜色为 $k$ 的球也被插入。
在颜色 $<i$ 的球全都插入序列时，我们要插入颜色为 $i$ 的球，设
$$
n_i=\sum_{j=1}^{i-1}c_i.
$$
显然插入完毕后序列中最后一个球必为颜色 $i$，那么不妨先将其插入序列的末端。那么剩余 $c_i-1$ 个求要插入到前面 $n_i$ 个球的 $n_i+1$ 个缝隙中，等价于用 $n_i$ 个球将 $c_i-1$ 个球隔开，由插板法易得有 $\dbinom{n_i+c_i-1}{n_i}$ 种方法。
故最终方法数为
$$
\prod_{i=1}^k\dbinom{n_i+c_i-1}{n_i}.
$$
时间复杂度 $\Theta(n^2)$（用于初始化组合数）。
## AC 代码
```c++
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int C[1001][1001];
long long answer=1;
int n,k;
int main(){
for(int i=0;i<=1000;i++){
C[i][0]=1;
for(int j=1;j<=i;j++)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
scanf("%d",&k);
for(int i=1;i<=k;i++){
int c;
scanf("%d",&c);
answer*=C[c+n-1][n];
n+=c,answer%=mod;
}
printf("%lld\n",answer);
return 0;
}
```