Polynomial coefficients

Polynomial coefficients

时间: 1ms        内存:64M

描述:

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

P = (x1 + x2 + ... + xk)n

输入:

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 x1n1x2n2...xknk in expansion of the polynomial ((x1 + x2 + ... + xk)n.

示例输入:

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;
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注