https://www.luogu.com.cn/problem/P3803

\(FFT/NTT\)

\(FFT:\)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define N 10000005
using namespace std;
double Pi=acos(-1.0);
struct virt
{
    double x,y;
    virt operator + (virt b)
    {
        return (virt){x+b.x,y+b.y};
    }
    virt operator - (virt b)
    {
        return (virt){x-b.x,y-b.y};
    }
    virt operator * (virt b)
    {
        return (virt){x*b.x-y*b.y,x*b.y+y*b.x};
    }
}a[N],b[N];
int n,m,q,l,s,r[N];
void FFT(virt *a,double t)
{
    for (int i=0;i<s;i++)
        if (i<r[i])
            swap(a[i],a[r[i]]);
    for (int mid=1;mid<s;mid <<=1)
    {
        virt wn=(virt){cos(Pi/mid),t*sin(Pi/mid)};
        for (int j=0;j<s;j+=(mid << 1))
        {
            virt w=(virt){1.0,0.0};
            for (int k=0;k<mid;k++,w=w*wn)
            {
                virt x=a[j+k],y=w*a[j+k+mid];
                a[j+k]=x+y;
                a[j+k+mid]=x-y;
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=0;i<=n;i++)
        scanf("%lf",&a[i].x);
    for (int i=0;i<=m;i++)
        scanf("%lf",&b[i].x);
    l=0;
    s=1;
    while (s<=n+m)
    {
        l++;
        s <<=1;
    }
    for (int i=0;i<s;i++)
        r[i]=(r[i >> 1] >> 1)|((i&1) << (l-1));
    FFT(a,1.0);
    FFT(b,1.0);
    for (int i=0;i<=s;i++)
        a[i]=a[i]*b[i];
    FFT(a,-1.0);
    for (int i=0;i<=n+m;i++)
        printf("%d ",(int)(a[i].x/(double)s+0.5));
    putchar(‘\n‘);
    return 0;
}

Luogu3803 【模板】多项式乘法（FFT）

原文：https://www.cnblogs.com/GK0328/p/13390265.html