joj 1013 Polynomial Multiplication多项式乘法的计算

 1013: Polynomial Multiplication

---

Result TIME Limit MEMORY Limit Run Times AC Times JUDGE

	3s	8192K	4373	753	Standard

A polynomial is a sum of terms, where each term is a coefficient multiplied by the variable x raised to some nonnegative integer power. The largest such power is referred to as the degree of the polynomial. For example: x^3+x^2+x+1, x^3+x, x^2, and 1 are all polynomials.

Input

A positive integer denoting the number of cases.
(The degree of polynomial 1) followed by the value of each coefficient for polynomial 1.
(The degree of polynomial 2) followed by the value of each coefficient for polynomial 2.
No polynomial will have degree greater than five. All coefficients will be greater than or equal to zero and less than 65536. Each polynomial will be on a separate line. A blank line will separate each case.

Output

The product of polynomial 1 and polynomial 2. The caret symbol (^) should be used to denote exponentiation. That is, x^2 means x*x. But, instead of x^1, just use x, and instead of x^0, use nothing. Terms where the coefficient is 0 must be omitted.

Example

In this example we multiply the following two sets of polynomials:
x^4+2x^3+x^2+5x and x^3+2x^2+1
x^3+x+1 and 2x^3+x+2

Input

2
4 1 2 1 5 0
3 1 2 0 1

3 1 0 1 1
3 2 0 1 2

Output

x^7 + 4x^6 + 5x^5 + 8x^4 + 12x^3 + x^2 + 5x
2x^6 + 3x^4 + 4x^3 + x^2 + 3x + 2

/*
	 多项式的乘法，
	 恶心的是输出为表达式的形式
*/
#include <iostream>
#include <string>
using namespace std;

int array[2][6];
int res[12];
int times,degree1,degree2;
void printRes(int * result)
{
	//j为结果系数不为零的最低次
		int j = 0,i;							//将j初始化为零
		for(i=0; i<=degree1+degree2; i++)		//计算j
			if(result[i]!=0){
				j = i;
				break;
			}

/*				打印多项式                */
		for(i=degree1+degree2; i>=j; i--){		
			if(i!=1&&i!=0){				//打印一般情况
				if(result[i]!=0){		//如果系数不为零打印结果
					if(result[i]!=1)	//如果系数不为1打印系数
						cout<<result[i];
					cout<<"x^"<<i;		
					if(i!=j)			//如果不是最后一项打印" + "
						cout<<" + ";
				}
			}
			else if(i==1){				//打印1次项，因为后面没有^1
				if(result[i]!=0){		//如果系数不为零打印结果
					if(result[i]!=1)	//如果系数不为1打印系数
						cout<<result[i];
					cout<<"x";
					if(j!=1)			//如果不是最后一项打印" + "
						cout<<" + ";
				}
			}
			else{						//打印常数项
				if(j==0)				//如果结果只有常数项直接打印常数
					cout<<result[i];	
				else if(result[i]!=0)	//如果结果中不只有常数项且常数项不为零打印常数项
					cout<<result[i];
			}
		}
/*				打印完毕				*/
			cout<<endl;
}

int main()
{	
	freopen("in.txt","r",stdin);
	cin >> times;

	for(int i=0;i<times;i++)
	{
		memset(res,0,sizeof(res));
		memset(array,0,sizeof(array));		

		cin >>degree1;
		for(int i=0;i<=degree1;i++)
			cin >> array[0][i];
		
		cin >>degree2;
		for(int j=0;j<=degree2;j++)
			cin >> array[1][j];

		for(int m=degree1;m>=0;m--)
		{
			for(int n=degree2;n>=0;n--)
			{
				/*
					array[0][m]对应的元素度是 degree1-m
					array[1][n]对应的元素度是 degree2-n
					所以对应的的是res[degree1 -m + degree2 - n]，res数组中存放的是对应的系数
				*/
				res[degree1 -m + degree2 - n] += array[0][m] * array[1][n]; //关键是此处
			}
		}
		printRes(res);
	/*	int u = 0;
		for(u=0;u< degree1 + degree2;u++)
			if(res[u] != 0)
				break;
		
		for(int k= degree1 + degree2;k>=u;k--)
		{
			if(res[k] == 0)
				continue;
			if(res[k] != 1)
				cout << res[k];
			if(k> 1) //u=2时候会出错
				cout <<"x^"<<k<< " + ";
			if(k ==  1)
				if(u == 0 )
					cout <<"x + ";
				else
					cout <<"x";
		}		
		cout << endl;*/
	}
	fclose(stdin);
	return 0;
}