codeforces 553A Kyoya and Colored Balls 组合数学

本文主要是介绍codeforces 553A Kyoya and Colored Balls 组合数学，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

有k种球，每种球有a[i]个。现在它们都放到一个袋子里，要求取出来的时候，第i种球完全取出来要在第i+1种球前面。问你有多少种取法。

思路：

比赛时没想出来。。。结果其实是很简单的。

倒过来统计就好了。

假设n = sum(a[i]);

首先先看第k种球，如果先把其中一个球放到最后一个位置，那么剩下的a[k]-1个球就是随便放，则有c[n-1][a[k]-1]种放法。

然后我们感受一下，如果把已经放了球的位置从n个位置中拿走，那是不是就生成了n-a[k]个连续空位置。

那么问题变回把第k-1种的其中一个球放到剩余的最后一个位置，然后有c[n-a[k]-1][a[k-1]-1]种放法；

……

最后将组合数乘起来即可。

code：

#include <bits/stdc++.h>
using namespace std;const int N = 1005;
const int MOD = 1e9+7;
typedef long long LL;int k;
int a[N];
LL c[N][N];
void preDeal() {c[0][0] = 1;for(int i = 1;i < N; i++) {c[i][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;}
}
int main() {preDeal();cin>>k;int tol = 0;for(int i = 0;i < k; i++){cin>>a[i];tol += a[i];}LL res = 1;for(int i = k-1;i > 0; i--) {res *= c[tol-1][a[i]-1];res %= MOD;tol -= a[i];}cout<<res<<endl;return 0;
}

这篇关于codeforces 553A Kyoya and Colored Balls 组合数学的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---