[UVA][math] 911 - Multinomial Coefficients
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;
}