题解 P2553 【[AHOI2001]多项式乘法】

· · 题解

看到题第一眼，就知道这是个暴力处理多项式然后用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;
}