Polynomial coefficients

code

6 年前

时间： 1ms 内存：64M

描述：

This problem seeks the coefficients resulting from the expansion of the polynomial

P = (x₁ + x₂ + ... + x_k)ⁿ

输入：

The input will consist of a set of pairs of lines. The first line of the pair consists of two integers n and k separated with space ( 0 < k, n < 13). These integers define the power of the polynomial and the number of variables. The second line in each pair consists of k non-negative integers n1,..., nk, where n1 + ... + nk = n.

输出：

For each input pair of lines the output line should consist of one integer, the coefficient of the monomial x₁^n₁x₂^n₂...x_k^n_k in expansion of the polynomial ((x₁ + x₂ + ... + x_k)ⁿ.

示例输入：

2 2
1 1
2 12
1 0 0 0 0 0 0 0 0 0 1 0

示例输出：

2
2

提示：

参考答案（内存最优[748]）：

#include"stdio.h"
long c(int n,int m)
{
	int i;
	long s=1;
	for(i=1;i<=n;i++)
		s*=i;
	for(i=1;i<=m;i++)
		s/=m;
	return s;
}	
int main()
{	
	int n,k,x;
	long s;
	while(scanf("%d%d",&n,&k)!=EOF)
	{
		s=1;
		while(k--)
		{
			scanf("%d",&x);
			s*=c(n,x);
			n-=x;
		}
		printf("%ld\n",s);
	}
	return 0;
}

参考答案（时间最优[0]）：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int  ans[55],m,k,a;
void solve()
{
    ans[0] = 1;
    for (int i = 1; i < 13; i++)
        ans[i] = ans[i-1] * i;
}
int main()
{
    int n,k;
    solve();
    while (~scanf("%d%d",&n,&k))
    {
        a = ans[n];
        for (int i = 0; i < k ; i++)
        {
            int  b;
            scanf("%d",&b);
            a/= ans[b];
        }
        printf("%d\n",a);
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。