Codeforces Round #309 (Div. 1) A（组合数学）

题目：http://codeforces.com/contest/553/problem/A

题意：给你k个颜色的球，下面k行代表每个颜色的球有多少个，规定第i种颜色的球的最后一个在第i-1种颜色的球的最后一个的前面

思路：首先我们想如果是第i种颜色，我们首先必须把这个颜色留下一个，留下的这个球前面的球的个数是前面颜色的总和+这个颜色数-1，

我们想这个颜色的位置数如何安排，即 C（总座位数，要安排的个数），i-1种颜色也是相同的道理，所以我们推出公式

累加球的个数 sum

当前颜色的球的个数num

那么当前颜色的安排个数 即  C（sum-1,num-1）

然后累乘所有的方案数即是答案

这里我们是用卢卡斯定理求的大组合数取模

#include<cmath>
#include<cstdio>
#define ll long long
#define mod 1000000007
using namespace std;
const int maxn = 10005;
ll dp[maxn],inv[maxn],fac[maxn],inv_fac[maxn];
void init()
{
    inv[0]=inv[1]=inv_fac[0]=fac[0]=1;
    dp[1]=0;dp[2]=1;
    for(int i=2; i<maxn; i++) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
    for(int i=1; i<maxn; i++) fac[i]=fac[i-1]*i%mod;
    for(int i=1; i<maxn; i++) inv_fac[i]=inv_fac[i-1]*inv[i]%mod;
    for(int i=3; i<maxn; i++) dp[i]=(i-1)*(dp[i-2]+dp[i-1])%mod;
}
ll C(int n,int m)
{
    return fac[n]*inv_fac[m]%mod*inv_fac[n-m]%mod;
}
int main()
{
    init();
    ll n,x;
    ll sum=0;
    ll flag=1; 
    scanf("%lld",&n);
    for(int i=0;i<n;i++){
        scanf("%lld",&x);
        sum+=x;
        flag=(flag*C(sum-1,x-1))%mod; 
    } 
    printf("%lld",flag);
}