10105 - Polynomial Coefficients

[Moni]

I want to solve 10105 in recursive approach. If anyone of you have solved it or want to solve it in recursive way welcome for discussion.
I need some help

[Moni]

We all know:

Code: Select all

(a+b)^2 = a^2 + 2*a*b + b^2;

We can extend this like:

Code: Select all

(p+q+r)^2 = {p + (q+r)}^2;

Now think p = a and (q+r) = b;

And this can be done in recursive approach. Have anybody done this or can anyone help me to do ???

[r.z.]

do you know what shoul be the output?
I don't understand the english.....

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

[UFP2161]

Don't know if you have solved this yet, but it has something to do with combinations (look back at binomial expansion and it's relation to a combination, and generalize)

[Rakot2005]

hi all!
I submitted my code and get WA, and i do not understand why
i use polynomial theorem - Binomial theorem.
C(n)_n1n2..nk= n!/П(ni)!
i do not understand, where a mistake...

[Antonio Ocampo]

You must use "long long".

Hope it helps

[Rakot2005]

i use double.

[Antonio Ocampo]

Maybe, you have a precision error. Isn

[Rakot2005]

i use double ,because i use division in the for cycle and intermediate state of results may be double.

give to me critical tests, please

[Rakot2005]

i got Accepted !!
i converted a double to long long in cout.
but i don't understand why giving out from double variable it is wrong ?

[murkho]

Hi dear,
If you can help me to find out the bugs of my program i will be thankful to U.

Code: Select all

//Name:polynomial coefficient....
//No: 10105....................


#include<stdio.h>



int main()
{
int in[10000],k,n,flag = 0,i;
long factorial[13] = {0,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600};
while(scanf("%d %d",&n,&k) ==2 )
	{
		flag = 0;
	 for(i = 0;i<k;i++)
		{
		 scanf("%d",&in[i]);
		 if(in[i] >1)
			{
			flag = 1;
			//break;		 
			}
	 
	 
		}

	 if(flag ==1)
		printf("%ld\n",0);
	
	 else
		printf("%ld\n",factorial[n]);	




	}	



return 0;
}

[Raj Ariyan]

Hi Murkho,
I think ur algo is not ok. Ya, u needs factorial upto 12 but not in this way. Try to find out the algo from any mathematical site like mathworld etc.. And one thinks 1!=1, and 0!=1 and there is no output of 0. Hope it helps. Good Luck.

[sds1100]

Code: Select all

#include <fstream.h>
int a[100000],k,n; 
int f[13] = {1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600};
void main() 
{ 
	int i,t=0;
	while(cin >> n >> k){ 
		t=0;
		for(i=0;i<k;i++) 
		{ 
			cin >> a[i];
			if(a[i]>1) 
			{ 
				t=1; 
			} 	
		} 
		if(t==1)cout << 0 << endl;
		else cout << f[n] << endl;
	} 
} 

...help me.. ... Why wa

[Darko]

Check this out:
http://mathworld.wolfram.com/Multinomia ... cient.html

And you just print f[n] on any input (or 0 for some reason)?

Darko

[flehns]

Code: Select all

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

double fact(double n) {
    if (n <= 1)
        return (double)1;
    return (n * fact(n - 1));
}

int main()
{
	int k, n;
	vector<int> output;
	vector<int>::iterator outputIter;

	while(cin >> n >> k)
	//cin >> n >> k;
	//while((n != 0) && (k != 0))
	{
		int x;
		double C;
		double productNis = 1;
		vector<int> ni;
		for(int i = 0; i < k; i++)
		{
			cin >> x;
			ni.push_back(x);
		}
		
		for(int i = 0; i < k; i++)
		{
			productNis = productNis * fact(ni.at(i));
		}

		C = fact(n)/productNis;
		output.push_back(C);
		//cin >> n >> k;
	}

	for(outputIter = output.begin(); outputIter != output.end(); outputIter++)
		cout << *outputIter << " \n";
}

I tried to implement the example from the website linked on the previous post. It seems to work on my computer with VS2005... Can someone please tell my why this is giving me a compile error for the judge?? Thanks for any help.