Problem G

Multinomial Coefficients

One of the first formulas we were taught in high school mathematics is . Later on, we learned that this is a special case of the expansion , in which the coefficient of is the number of combinations of things taken at a time. We never learned (at least I never did...) what happens if instead of a binomial we have a multinomial .

Problem

Your task is to write a program that, given a multinomial , , computes the coefficient of a given term in the expansion of , . The given term is specified by a sequence of integer numbers , , , , representing the powers of , , , in the expansion. Note that . For example, the coefficient of in is .

Input

The input file contains several test cases, each of them with three lines. The first line contains a number representing the value of . The second line contains a number representing the value of . The third line contains numbers, representing the values of , , ,. All test cases are such that and the computed coefficient is less than .

Output

For each test case, write to the output one line. This line contains one integer number representing the value of the coefficient of the term in the expansion of .

Sample Input 1

4

3

1 2 1

Sample Output 1

12

Sample Input 2

7

4

2 3 0 2

Sample Output 2

210

---

Pedro Guerreiro, MIUP'2003
(Portuguese National ACM Programming Contest)

不能使用 N! / (x1!x2!...xn!), x1+x2+x3+ ... + xn = n
用陣列表示，然後慢慢消去。

#include <stdio.h>

int gcd(int x, int y) {
    int t;
    while(x%y)
        t = x, x = y, y = t%y;
    return y;
}
int main() {
    int i, j, k;
    int n, m, x;
    while(scanf("%d %d", &n, &m) == 2) {
        int A[105], sum = 0;
        for(i = 1; i <= n; i++)
            A[i] = i;
        while(m--) {
            scanf("%d", &x);
            sum += x;
            for(i = 2; i <= x; i++) {
                j = i;
                for(k = 2; k <= n; k++) {
                    int g = gcd(A[k], j);
                    A[k] /= g;
                    j /= g;
                }
            }
        }
        long long ret = 1;
        if(sum != n) {ret = 0;}
        else {
            for(i = 1; i <= n; i++)
                ret *= A[i];
        }
        printf("%lld\n", ret);
    }
    return 0;
}