Codeforences #309 C(div2)

In the first sample, we have 2 balls of color 1, 2 balls of color 2, and 1 ball of color 3. The three ways for Kyoya are:

1 2 1 2 3
1 1 2 2 3

2 1 1 2 3

【题意】给了n个球，其中n个球***有k种颜色，现在要用n个球形成一些排列，a[i]表示颜色为i的有a[i]个，num之和为n，现在问你这n个小球有多少种排列方式，满足第i种颜色最后一个球后面的球的颜色是i+1。

【分析】先考虑第k种颜色，那么一定有一个颜色为k的小球放在最后。

【状态表示】dp[i]表示前i种颜色的方法总数。

【状态转移】dp[i+1] = dp[i]*(C[sum(i+1)-1][a[i+1]-1]);

【说明】C[i][j]表示组合数，可以提前预处理，sum[i+1]表示2前i+1种小球颜色种数，a[i+1]代表颜色为i+1的小球个数。

【参考博客】http://blog.csdn.net/kirito_acmer/article/details/46830331

【AC代码】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
const int N = 1002;
ll C[N][N];
ll dp[N];
void init()
{
    for(int i=1; i<=1000; i++) C[i][0]=1;
    for(int i=1; i<=1000; i++)
    {
        for(int j=1; j<=i; j++)
        {
            if(i==j)C[i][j]=1;
            else
                C[i][j] = (C[i-1][j]+C[i-1][j-1])%mod;
        }
    }
}
int main()
{
    int n,a[1005];
    ios::sync_with_stdio();cin.tie(0);
    init();
    cin>>n;
    for(int i=1; i<=n; i++)cin>>a[i];
    ll sum=a[1],ans=1;
    for(int i=2; i<=n; i++)
    {
        sum = sum + a[i];
        ans = ((ans%mod)*(C[sum-1][a[i]-1]%mod))%mod;
    }
    cout<<ans<<endl;
    return 0;
}