分析

当计算两个项数较多的多项式的乘积时，如果使用传统系数相乘，时间复杂度为O($n^2$)，会超时。

超时 代码(可过6个点)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10,M= 2e5+10;
int a[M],b[M],l1,l2;
char s[N];
void print(int a[])
{
    int k=M-1;
    while(k && !a[k]) k--;
    for(int i=k;i>=0;i--) cout<<a[i];
}
void mul(int a[],int b[])
{
    int t=0,temp[M];
    memset(temp,0,sizeof temp);
    for(int i=0;i<l1;i++)
        for(int j=0;j<l2;j++)
            temp[i+j]+=a[i]*b[j];

    for(int i=0;i<l1+l2;i++)
    {
        t+=temp[i];
        temp[i]=t%10;
        t/=10;
    }

    memcpy(a,temp,sizeof temp);
}
int main()
{
    scanf("%s",s);
    l1=strlen(s);
    for(int i=0;i<l1;i++) a[l1-i-1]=s[i]-'0';

    scanf("%s",s);
    l2=strlen(s);
    for(int i=0;i<l2;i++) b[l2-i-1]=s[i]-'0';

    mul(a,b);
    print(a);
    return 0;
}

所以此时要使用FFT，这样就可以完美解决了。
FFT详解

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 300010,M= 3000010;
const double PI = acos(-1);
int n,m;
char s[N];  //读入每个数
int Lim = 1; //limit是数组长度
int L; //二进制的位数
int R[N],ans[N],k;  //R[]:反转后的数组，ans[]为答案数组，k为答案数组的位数

struct Complex{ //定义复数
    double x,y;     //实部、虚部
    Complex operator+(const Complex &p)const{   //复数加法
        return {x+p.x,y+p.y};
    }
    Complex operator-(const Complex &p)const{   //复数减法
        return {x-p.x,y-p.y};
    }
    Complex operator*(const Complex &p)const{   //复数乘法
        return {x*p.x-y*p.y,x*p.y+y*p.x};
    }
}a[M],b[M];
void print(int a[])
{
    while(k && !ans[k]) k--;
    for(int i=k;i>=0;i--) cout<<ans[i];
}
inline void FFT(Complex a[],double type)    //快速傅里叶变换
{
    for(int i=0;i<Lim;i++)  //求出要迭代的序列
    {
        if(i<R[i]) swap(a[i],a[R[i]]);
    }
    for(int mid=1;mid<Lim;mid<<=1)  //待合并区间的中点
    {
        Complex wn={cos(PI/mid),type*sin(PI/mid)};  //单位根
        for(int pos=0;pos<Lim;pos+=mid*2)   //mid*2是区间的右端点
        {
            Complex w={1,0};    //幂    
            for(int k=0;k<mid;k++,w=w*wn)   //枚举左半部分 
            {
                Complex x=a[pos+k];
                Complex y=w*a[pos+mid+k];
                a[pos+k]=x+y;   //蝴蝶变换
                a[pos+mid+k]=x-y;
            }
        }
    }
}
int main()
{
    scanf("%s",s);  //读入第一个数
    n=strlen(s);
    for(int i=0;i<n;i++) a[n-i-1].x=s[i]-'0';   //存储在复数a[]的对应实部

    scanf("%s",s);  //读入第二个数
    m=strlen(s);
    for(int i=0;i<m;i++) b[m-i-1].x=s[i]-'0';   //存储在复数b[]的对应实部

    while(Lim<n+m)  //求出数组长度
    {
        Lim<<=1;
        L++;
    }

    // 在原序列中 i 与 i/2 的关系是 ： i可以看做是i/2的二进制上的每一位左移一位
    // 那么在反转后的数组中就需要右移一位，同时特殊处理一下复数 
    for(int i=0;i<=Lim;i++)
    {
        R[i]= (R[i>>1]>>1) | ( (i&1)<<(L-1) );
    }

    FFT(a,1),FFT(b,1);  //对数组a[]和数组b[]进行DFT，转化为点值表示

    for(int i=0;i<=Lim;i++)
    {
        //对应项相乘，O(n)得到点值表示的多项式的解
        a[i]=a[i]*b[i];
    }

    FFT(a,-1);  //a[]还原成系数表示，这个过程叫做IDFT
    k=0;    //统计答案位数
    for(int i=0,t=0;i<=Lim || t;i++)    
    {
        t+=round(a[i].x/Lim);   //对答案的实部进行计算，每位采取4舍去5入
        ans[k++]=t%10;
        t/=10;
    }

    print(ans);
    return 0;
}