C : Kyoya and Colored Balls CodeForces - 553A

最简洁的题意：
C. Kyoya and Colored Balls
Time Limit: 2000ms
Memory Limit: 262144KB
64-bit integer IO format: %I64d Java class name: (Any)
Submit Status
Kyoya Ootori has a bag with n colored balls that are colored with k different colors. The colors are labeled from 1 to k. Balls of the same color are indistinguishable. He draws balls from the bag one by one until the bag is empty. He noticed that he drew the last ball of color i before drawing the last ball of color i + 1 for all i from 1 to k - 1. Now he wonders how many different ways this can happen.

Input
The first line of input will have one integer k (1 ≤ k ≤ 1000) the number of colors.

Then, k lines will follow. The i-th line will contain ci, the number of balls of the i-th color (1 ≤ ci ≤ 1000).

The total number of balls doesn’t exceed 1000.

Output
A single integer, the number of ways that Kyoya can draw the balls from the bag as described in the statement, modulo 1 000 000 007.

Sample Input
Input
3
2
2
1
Output
3
Input
4
1
2
3
4
Output
1680
Hint
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

1 2 1 2 3
1 1 2 2 3
2 1 1 2 3

题目大意为，有n种球，编号分别为1234….n，每种球有ci个，问有几种取法，能把盒子里的球拿完，要求是每次取完一种球前，编号比他小的球都取完。

思路：从小往大排列，首先一开始只有一个格子可以放，放入（c1-1）个一号球，并把最后一个一号球放最后，这样一共有（c1+1）个格子，然后在这么多格子里放入（c2-1）个二号球，并把最后一个二号球放在最后，这样一直到最后。
对于 n个格子里放m个球，打个表球行。n个格子放m个球 放的种类就是（n-1个格子放0,1,2,3,4,….mg个球）求和， 推倒一下很容易得到（n个格子放m个球）=（n-1格子放m个球）+(n格子放m-1个球)。这就是推导公式。

2 思路：可以知道涂颜色k的最后一个球一定在最后一个位置上，那么剩下的a[k]-1个球就可以在n-1个位置任意摆放，有C（a[k]-1,n-1）种放法。然后颜色为k-1的最后一个球就摆放在颜色为k球的前面一位，剩下的a[k-1]-1个球就可以在n-a[k]-1的位置上摆放，有C（a[k-1]-1,n-a[k]-1）种放法。

依次类推，直到所有的球都放完。那么答案就是上述的放法相乘然后取模。

但是对于C（m,n），虽然我们可以通过阶乘A（m,n）/A(m,m)计算，但是数据范围一大，long long范围下就存不下了，如果采用取模方式，就会出错。

所以我们想到了一个公式：C（m,n）=C(m,n-1)+C(m-1,n-1)。

那么我们就可以设一个数组来记录下C（m,n）的答案。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
using namespace std;

const int mod =  1e9+7;
const int maxn=  2005;
long long s[maxn][maxn]={0};
int a[maxn];
int main()
{
    for(int i=0;i<maxn;i++)
        s[i][0]=  1;
    for(int i=1;i<maxn;i++)
    {
        for(int j=1;j<=i;j++)
        {
            if(i==j)s[i][j] = 1;
            else if(i>j)
            s[i][j] = (s[i-1][j]+s[i-1][j-1])%mod;
        }
    }
    int t;
   cin>>t;
    int ans = 1;
    int sum = 0;
    for(int i=1;i<=t;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    for(int i=t;i>=1;i--)
    {
        //if(a[i]==0)a[i]++;
        ans = (ans*s[sum-1][a[i]-1])%mod;
        sum-=a[i];
        ans = ans%mod;
    }
    cout<<ans<<endl;
    return 0;
}