记录编号	16097	评测结果	WWWWWW
题目名称	多项式运算	最终得分	0
用户昵称	lc	是否通过	未通过
代码语言	C++	运行时间	1.827 s
提交时间	2010-04-19 17:58:24	内存使用	78.06 MiB

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn = 510,maxp = 9997;
char opt[10];
int num,Dir,X0,Total,Pos; char ch; bool Finish;
struct Hashtype
{
	int P,S;
}Hash[maxn][maxp],A[maxn][maxp];
int Len[maxn];


bool Number(char ch)
{
	return ch-'0'>=0 && ch-'0'<=9;
}

void Insert(int Pos,int num,int P)
{
	int T = P % maxp;
	while (Hash[Pos][T].P>=0)
	{
		if (Hash[Pos][T].P==P)
		{
			Hash[Pos][T].S += num; return;
		}
		T = (T + 3) % maxp;
	}
	
	Hash[Pos][T].P = P;
	Hash[Pos][T].S = num;
}


bool Dolast(int Pos)
{
	if (ch=='\n')
	{
		Insert(Pos,num*Dir,0); return true;
	}
	if (ch=='x')
	{
		scanf("%c",&ch);
		if (ch=='^')
		{
			scanf("%c",&ch);
			int P = 0;
			while (Number(ch))
			{
				P = P*10 + ch-'0';
				scanf("%c",&ch);
			}
			Insert(Pos,num*Dir,P);
			if (ch=='\n') return true;
			Dir = ch=='+'?1:-1;
		}//乘方
		else
		{
			Insert(Pos,num*Dir,1);
			if (ch=='\n') return true;
			Dir = ch=='+'?1:-1;
		}//+ -
	}
	else
	{
		Insert(Pos,num*Dir,0);
		Dir = ch=='+'?1:-1;
	}//无变量
	return false;
}

void Solve(int Pos)
{
	Dir = 1;
	while (true)
	{
		scanf("%c",&ch);
		if (ch=='-')
		{
			Dir = -1; scanf("%c",&ch);
			if (ch=='1')
			{
				Finish = true; return;
			}
		}
		
		if (Number(ch))
		{
			num = 0;
			while (Number(ch))
			{
				num = num*10 + ch-'0';
				scanf("%c",&ch);
			}
			if (Dolast(Pos)) return;
		}
		else
		{
			num = 1;
			if (Dolast(Pos)) return;
		}
	}
}

void prep()
{
	scanf("%s\n",&opt);
	if (opt[0]=='l') exit(0);
	if (opt[0]=='e') scanf("%d\n",&X0);
	Finish = false;
	memset(Hash,-1,sizeof(Hash));
	
	if (opt[0]=='e') {Pos = 1; Solve(1); return;}
	
	Pos = 0;
	while (!Finish)
	{
		Pos++; Solve(Pos);
	}
}

void Out(int Pos,int i)
{
	if (A[Pos][i].S==0) return;
	if (A[Pos][i].S==-1) printf("-");
	if (abs(A[Pos][i].S)!=1) printf("%d",A[Pos][i].S);
	if (A[Pos][i].P) printf("x");
	if (A[Pos][i].P>1) printf("^%d",A[Pos][i].P);
}

void print()
{
	Total++; printf("%d:",Total);
	for (int i=Len[Pos+1]; i>1; i--)
	{
		Out(Pos+1,i);
		if (A[Pos+1][i-1].S>0) printf("+");
	}
	Out(Pos+1,1);
	printf("\n");
}

int Power(int x,int y)
{
	int res = 1;
	for (int i=1; i<=y; i++) res *= x;
	return res;
}

void Collect(int Pos)
{
	Len[Pos] = 0;
	for (int i=0; i<maxp; i++)
		if (Hash[Pos][i].P!=-1)
		{
			Len[Pos]++;
			A[Pos][Len[Pos]].P = Hash[Pos][i].P;
			A[Pos][Len[Pos]].S = Hash[Pos][i].S;
		}
}

void work()
{
	for (int i=1; i<=Pos; i++)
	{
		Collect(i);
	}
	
	if (opt[0]=='a')
	{
		for (int i=1; i<=Pos; i++)
			for (int j=1; j<=Len[i]; j++)
			Insert(Pos+1,A[i][j].S,A[i][j].P);
		Collect(Pos+1);
	}
	if (opt[0]=='s')
	{
		for (int j=1; j<=Len[1]; j++)
			Insert(Pos+1,A[1][j].S,A[1][j].P);
		for (int i=2; i<=Pos; i++)
			for (int j=1; j<=Len[i]; j++)
				Insert(Pos+1,-A[i][j].S,A[i][j].P);
		Collect(Pos+1);
	}
	if (opt[0]=='e')
	{
		for (int i=1; i<=Pos; i++)
		{
			int Sum = 0;
			for (int j=1; j<=Len[i]; j++)
				Sum += A[i][j].S * Power(X0,A[i][j].P);
			Total++; printf("%d:",Total);
			printf("%d\n",Sum);
		}
	}
	if (opt[0]=='m')
	{
		for (int j=1; j<=Len[1]; j++)
			Insert(Pos+1,A[1][j].S,A[1][j].P);
	
		for (int i=2; i<=Pos; i++)
		{
			for (int j=1; j<=Len[i]; j++)
				for (int k=1; k<=Len[Pos+1]; k++)
				{
					Insert(Pos+1,A[i][j].S * A[Pos+1][k].S,A[i][j].P + A[Pos+1][k].P);
				}
			
			Collect(Pos+1);
			memset(Hash[Pos+1],-1,sizeof(Hash[Pos+1]));
		}
	}
	if (opt[0]!='e') print();
}

int main()
{
	freopen("ploy.in","r",stdin);
	freopen("ploy.out","w",stdout);
	while (true)
	{
		prep();
		work();
	}
	return 0;
}