自动搬运

查看原文

来自洛谷，原作者为

	Dispwnl **

搬运于2025-08-24 21:39:00，当前版本为作者最后更新于2018-06-19 16:30:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到题第一眼，就知道这是个暴力处理多项式然后用fft搞就行了。。。

但是有许多坑点，比如输入字符串中没有'*'就什么也不输出题目就™不能讲清楚吗

因为这个WA了好几次，又因为只有一个数据点，每次都提示输出多了，我也看不了别人代码对一下。。。

最后在网上找了一个博客，试了几组数据都正确并且ta还不能处理没有括号的情况

看到ta的代码中有一行：

if(ppos == std::string::npos) continue;

这是干啥啊大兄弟。。。似乎是判断有没有'*'？

然后加上就过了。。。这种垃圾题还是别出了QAQ

代码：

# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
using namespace std;
const int MAX=1e6+1;
const double Pi=acos(-1.0);
struct complex{
	double x,y;
	complex(double X=0,double Y=0){x=X,y=Y;}
}a[2][MAX];
int n,m,l,lim=1;
int r[MAX],len[MAX],ans[MAX];
complex operator+ (complex x,complex y)
{
	return complex(x.x+y.x,x.y+y.y);
}
complex operator- (complex x,complex y)
{
	return complex(x.x-y.x,x.y-y.y);
}
complex operator* (complex x,complex y)
{
	return complex(x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x);
}
void fft(complex *A,int tt)
{
	for(int i=0;i<lim;++i)
	  if(i<r[i]) swap(A[i],A[r[i]]);
	for(int i=1;i<lim;i<<=1)
	  {
	  	complex w1(cos(Pi/i),tt*sin(Pi/i));
		for(int l=i<<1,j=0;j<lim;j+=l)
		  {
	  		complex w(1,0);
	  		for(int k=0;k<i;++k,w=w*w1)
	  		  {
	  		  	complex x=A[j+k],y=w*A[j+i+k];
	  		  	A[j+k]=x+y,A[j+i+k]=x-y;
			  }
	  	  }
	  }
	if(tt==-1)
	for(int i=0;i<lim;++i)
	  A[i].x=(int)(A[i].x/lim+0.5);
}
int main()
{
	string s;
	while(getline(cin,s))
	{
		bool fl=0;
		int L=s.length(),num=0;
		for(int i=0;i<L;++i)
		  if(s[i]=='*')
		  {
		  	fl=1;
		  	break;
		  }
		if(!fl) continue;
		memset(a,0,sizeof(a));
		memset(len,0,sizeof(len));
		memset(ans,0,sizeof(ans));
		for(int i=0,tt=0;i<L;i+=tt)
		  {
		  	tt=0;
		  	int x=0;
		  	if(isdigit(s[i]))
			{
				int j=i;
		  		while(isdigit(s[j])) ++tt,x=x*10+s[j++]-48;
		  		while(s[j]==' ') ++j;
		  		if(s[j]=='a')
		  		{
		  			j+=2,tt+=2;
		  			int y=0;
		  			while(isdigit(s[j])) ++tt,y=y*10+s[j++]-48;
		  			len[num]=max(len[num],y);
					a[fl][y].x+=x;
				}
				else if(s[j]=='+'||s[j]==')'||s[j]=='*'||j==L) a[fl][0].x+=x;
			}
			if(s[i]=='*'||i+(tt?tt:1)-1==L-1)
			{
				if(s[i]=='*') ++tt;
				if(num>=1)
				{
					lim=1,l=0;
					memset(r,0,sizeof(r));
					while(lim<=len[num]+len[num-1]) lim<<=1,++l;
					for(int j=0;j<lim;++j)
					  r[j]=(r[j>>1]>>1)|((j&1)<<(l-1));
					fft(a[fl],1),fft(a[fl^1],1);
					for(int j=0;j<=lim;++j)
					  a[fl][j]=a[fl][j]*a[fl^1][j];
					fft(a[fl],-1);
					for(int j=0;j<=lim;++j)
					  a[fl][j].y=a[fl^1][j].y=a[fl^1][j].x=0;
					len[num]=len[num]+len[num-1];
				}
				++num,fl^=1;
			}
			if(!tt) ++tt;
		  }
		bool gg=0;
		for(int j=0;j<=len[num]+len[num-1];++j)
		  {
		  	ans[j]+=a[fl^1][j].x;
		  	if(a[fl^1][j].x!=0) gg=1;
		  }
		if(!gg)
		{
			printf("0\n");
			continue;
		}
		int Len1=0,Len2=0;
		for(int i=0;!ans[i];++i)
		  ++Len1;
		Len2=Len1;
		for(int i=Len1+1;ans[i]!=0;++i)
		  ++Len2;
		if(Len2!=Len1) printf("%da^%d",ans[Len2],Len2);
		for(int i=Len2-1;i>Len1;--i)
		  printf("+%da^%d",ans[i],i);
		if(!Len1)
		{
			if(Len2) printf("+%d\n",ans[0]);
			else printf("%d\n",ans[0]);
		}
		else
		{
			if(Len2!=Len1) printf("+%da^%d\n",ans[Len1],Len1);
			else printf("%da^%d\n",ans[Len1],Len1);
		}
	}
	return 0;
}