Codeforces Round #309 (Div. 1) A. Kyoya and Colored Balls

原题:http://codeforces.com/contest/553/problem/A

---

题目大意: k个颜色, n个球, 球之间没区别. 问怎么放能至少让一个i个颜色的球排在i+1的颜色的球的前边.

---

分析:这题目看起来是很拗口, 我看着发愣了一会儿才明白. 颜色是有顺序的.第i+1颜色的前边至少要有一个i颜色的球, 这个i不是固定的. 1<=i<=k-1, 所以题目也可以解释成,至少一组球是有序的, 这个有序不一定是连续的球. 因为i表示的颜色是个范围, 所以要用dp来做, 假设i = 1, 这时候就一种颜色, 因为球和球之间无区别, 所以答案是1. i = 2的时候, 因为要保持以上的条件, 所以我们选一个颜色为2的球,放到最后, 然后其他的无所谓.

(点一下,有清楚的图)

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int[] nums = IOUtils.readIntArray(in,n);
        int max = 1002;
        long[][] bio = new long[max][max];
        for (int i = 0; i < max; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0)
                    bio[i][j] = 1;
                else if (j == i)
                    bio[i][j] = 1;
                else
                    bio[i][j] = (bio[i-1][j-1] + bio[i-1][j])%1000000007; // mod 1000000007 is required
            }
        }
        long res = 1;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            res = (res * bio[sum+nums[i]-1][nums[i]-1]) % 1000000007; // mod 1000000007 is required
            sum += nums[i];
        }
        out.print(res);
    }