ACM – Uva10105 – 组合数 -

基本上是组合数裸题。。

给出$(x_1+x_2+x_3….x_k)^n$，要求计算$x_1^{n_1}x_2^{n_2}…x_k^{n_k}$的系数。

思想就是从一个算式中取出$n_k$，即$C_n^{n_k}$，然后减去$n_k$，如果直接相乘则会重复。

#include <bits/stdc++.h>
using namespace std;
// 大数，内存处理
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = ; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
const int maxn = 15;
int a[maxn];
int C[maxn][maxn];
void init()
{
    for(int i = ; i < maxn; i++)
    {
        C[i][] = C[i][i] = 1;
        for(int j = 1; j < i; j++) C[i][j] = C[i-1][j] + C[i-1][j-1];
    }
}
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int n, k;
    init();
    while(~scanf("%d%d", &n, &k))
    {
        for(int i = ; i < k;i ++) scanf("%d", &a[i]);
        int ans = 1;
        for(int i = ; i < k; i++) {
            ans *= C[n][a[i]];
            n -= a[i];
        }
        printf("%d\n", ans);
    }
    return ;
}