UVA 10105 Polynomial Coefficients(数论)

The Output

For each input pair of lines the output line should consist one integer, the coefficient by the monomialx1n1x2n2...xknk in expansion of the polynomial (x1+x2+...+xk)n.

Sample Input

2 2

1 1

2 12

1 0 0 0 0 0 0 0 0 0 1 0

Sample Output

2

2

题意：给定n,k。在给k个数nk。(x1 +x2 + x3 +...+xk) ^ n的展开式中x1^n1*x2^n2*...*xk*nk的系数。

思路：对于(x1 +x2 + x3 +...+xk) ^ n可以看成(Sk - 1 + xk) ^ n然后对于Sk - 1又能看成Sk - 2, xk -1。然后系数为Cn nk.这样一直求到n为0为止

代码：

#include   
#include   
const int N = 15;  
int c[N][N], n, k, nk[N];  
  
int cal(int n, int m) {  
    int a = 1, b = 1, num = m;  
    for (int i = 0; i < num; i ++) {  
        a *= n; n --;  
        b *= m; m --;  
    }  
    return a / b;  
}  
void init() {  
    for (int i = 1; i <= 12; i ++) {  
        for (int j = 0; j <= i; j ++) {  
            c[i][j] = cal(i, j);  
        }  
    }  
}  
  
int solve() {  
    int ans = 1;      
    for (int i = k; i >= 0; i --) {  
        ans *= c[n][nk[i]];  
        n -= nk[i];  
        if (n == 0)  
            return ans;  
    }  
    return ans;  
}  
  
int main() {  
    init();  
    while (~scanf("%d%d", &n, &k)) {  
        for (int i = 1; i <= k; i ++)  
            scanf("%d", &nk[i]);  
        printf("%d\n", solve());  
    }  
    return 0;  
}