in Blog & Problem

题目大意

• 有 $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$ 的球，设

显然插入完毕后序列中最后一个球必为颜色 $i$，那么不妨先将其插入序列的末端。那么剩余 $c_i-1$ 个求要插入到前面 $n_i$ 个球的 $n_i+1$ 个缝隙中，等价于用 $n_i$ 个球将 $c_i-1$ 个球隔开，由插板法易得有 $\dbinom{n_i+c_i-1}{n_i}$ 种方法。

故最终方法数为

时间复杂度 $\Theta(n^2)$（用于初始化组合数）。

AC 代码

#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;
}