传送门

这题就是普及暴力模拟板子FFT板子,只要把多项式读入进来FFT一下就好了(不会的右转P3803)

重点是读入,我本以为这个字符串里到处都有空格,这里提供一种简单思路:

因为里面可能有空格,所以用while和scanf读入连续的一段字符,如果读到数字就把这个系数(以及可能有的a的次数)抠出来,放在对应的多项式里

如果读到),如果这是第奇数个,那么后面的系数放到第二个多项式里,否则进行FFT并输出,并且让后面的系数放到第一个多项式里

注意多组数据要清空某些变量,数组

#include<bits/stdc++.h>

#define LL long long

#define db double

#define il inline

#define re register

using namespace std;

const int N=100000+10,M=270000+10;

const db pi=acos(-1);

il int rd()

{

  int x=0,w=1;char ch=0;

  while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

  while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

  return x*w;

}

struct comp

{

  db r,i;

  comp(){r=i=0;}

  comp(db nr,db ni){r=nr,i=ni;}

  il comp operator + (const comp &bb) const {return comp(r+bb.r,i+bb.i);}

  il comp operator - (const comp &bb) const {return comp(r-bb.r,i-bb.i);}

  il comp operator * (const comp &bb) const {return comp(r*bb.r-i*bb.i,r*bb.i+i*bb.r);}

}a[M],b[M];

int n,m,nn,l,rdr[M];

void fft(comp *a,int op)

{

  comp W,w,x,y;

  for(int i=0;i<nn;++i) if(i<rdr[i]) swap(a[i],a[rdr[i]]);

  for(int i=1;i<nn;i<<=1)

    {

      W=comp(cos(pi/i),sin(pi/i)*op);

      for(int j=0;j<nn;j+=i<<1)

        {

          w=comp(1,0);

          for(int k=0;k<i;++k,w=w*W)

            {

              x=a[j+k],y=w*a[j+k+i];

              a[j+k]=x+y,a[j+k+i]=x-y;

            }

        }

    }

}

il void work()

{

  m+=n;

  for(nn=1;nn<=m;nn<<=1) ++l;

  for(int i=0;i<nn;++i) rdr[i]=(rdr[i>>1]>>1)|((i&1)<<(l-1));

  fft(a,1),fft(b,1);

  for(int i=0;i<nn;++i) a[i]=a[i]*b[i];

  fft(a,-1);

  for(int i=m,z=0;i>=0;--i)

	{

	  LL x=(LL)(fabs(a[i].r)/nn+0.5);

	  if(x)

		{

		  if(!z) z=1;

		  else putchar('+');

		  if(i) printf("%llda^%d",x,i);

		  else printf("%lld",x);

		}

	}

  putchar('\n');

  memset(a,0,sizeof(a)),memset(b,0,sizeof(b)),l=n=m=0;

}

char cc[N];

int main()

{

  bool f=0;

  while(scanf("%s",cc)!=-1)

	{

	  int len=strlen(cc);

	  for(int i=0;i<len;++i)

		{

		  if(cc[i]>='0'&&cc[i]<='9')

			{

			  int x=0,y=0;

			  while(cc[i]>='0'&&cc[i]<='9') x=(x<<3)+(x<<1)+(cc[i]^48),++i;

			  --i;

			  if(cc[i+1]=='a')

				{

				  ++i,++i,++i;

				  while(cc[i]>='0'&&cc[i]<='9') y=(y<<3)+(y<<1)+(cc[i]^48),++i;

				  --i;

				}

			  if(!f) n=max(n,y),a[y].r=x;

			  else m=max(m,y),b[y].r=x;

			}

		  else if(cc[i]==')')

			{

			  f^=1;

			  if(!f) work();

			}

		}

	}

  return 0;

}