【Luogu1919】 A*B Problem升级版（FFT）

题面戳我

题解

把每个数都直接看做一个多项式，每一位就是一项

现在求用FFT求出卷积

然后考虑一下进位就可以啦

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<complex>

#include<set>

#include<map>

#include<vector>

using namespace std;

#define MAX 140000

complex<double> a[MAX],b[MAX];

char s[MAX];

int M,l;

const double Pi=acos(-1);

int r[MAX],N;

int num[MAX];

inline void Init()

{

    scanf("%d",&N);scanf("%s",s);N--;

    for(int i=0;i<=N;++i)a[i]=s[N-i]-48;

    scanf("%s",s);

    for(int i=0;i<=N;++i)b[i]=s[N-i]-48;

}

void FFT(complex<double> *P,int opt)

{

    for(int i=0;i<N;++i)if(i<r[i])swap(P[i],P[r[i]]);

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

    {

        complex<double> W(cos(Pi/i),opt*sin(Pi/i));

        for(int p=i<<1,j=0;j<N;j+=p)

        {

            complex<double> w(1,0);

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

            {

                complex<double> X=P[j+k],Y=w*P[j+k+i];

                P[j+k]=X+Y;P[j+k+i]=X-Y;

            }

        }

    }

}

int main()

{

    Init();

    M=N+N;

    for(N=1;N<=M;N<<=1)l++;

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

    FFT(a,1);FFT(b,1);

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

    FFT(a,-1);

    for(int i=0;i<N;++i)num[i]=(int)(a[i].real()/N+0.5);

    //N=N+2;

    for(int i=0;i<N;++i)num[i+1]+=num[i]/10,num[i]%=10;

    while(!num[N-1])N--;

    for(int i=N-1;i>=0;--i)printf("%d",num[i]);

    return 0;

}