1. 题目

传送门=￣ω￣=

2. 题解

xzy 太蒻了，只会刷板题。

LUOGU 太坑了，居然输入还带前导 0！

代码：

#pragma GCC optimize("Ofast,no-stack-protector")
#include <bits/stdc++.h>
#define NS (200000)
using namespace std;
typedef complex<double> cpx;
int n,rev[NS],ans[NS],top;
char str[NS];
cpx c1[NS],c2[NS];
void tocpx(cpx*a)//将 str 反转并转化为复数
{
    for(int i=0;i<(n>>1);i++)swap(str[i],str[n-i-1]);
    for(int i=0;i<n;i++)a[i].real(str[i]-'0');
}
void FFT(cpx*a,int lg,int t)
{
    int len=(1<<lg);
    for(int i=0;i<len;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
    for(int l=1;l<len;l<<=1)
        for(int i=0;i<len;i+=(l<<1))
        {
            cpx w(1,0),wn(cos(M_PI/l),t*sin(M_PI/l)),t0,t1;
            for(int k=i;k<i+l;k++,w*=wn)
                t0=a[k],t1=a[k+l]*w,a[k]=t0+t1,a[k+l]=t0-t1;
        }
}
int main()
{
    scanf("%d%s",&n,str),tocpx(c1),scanf("%s",str),tocpx(c2),n--;//n 是次数，要-1
    int lg=0,len;while((1<<lg)<=(n<<1))lg++;
    len=(1<<lg);
    for(int i=0;i<len;i++)rev[i]=((rev[i>>1]>>1)|((i&1)<<(lg-1)));
    FFT(c1,lg,1),FFT(c2,lg,1);
    for(int i=0;i<len;i++)c1[i]*=c2[i];
    FFT(c1,lg,-1),top=(n<<1|1);
    for(int i=0;i<(n<<1|1);i++)ans[i]=c1[i].real()/len+0.5;
    for(int i=0;i<(n<<1|1);i++)if(ans[i]>=10)ans[i+1]+=ans[i]/10,ans[i]%=10;
    while(ans[top])
    {
        if(ans[top]>=10)ans[top+1]+=ans[top]/10,ans[top]%=10;
        top++;
    }
    while(!ans[top-1])top--;//判前导 0
    for(int i=top-1;i>=0;i--)printf("%d",ans[i]);
    return 0;
}