传送门 入门级别多项式基本操作，查阅了很多资料终于入门fft了！qwq code:
#include<bits/stdc++.h> using namespace std; const int N = 4 * 1e6 + 10; int n, m; int rev[N]; #define gc getchar int read() { int res = 0, f = 1; char ch = gc(); while (!isdigit(ch)) f ^= ch == '-', ch = gc(); while (isdigit(ch)) res = (res + (res << 2) << 1) + (ch ^ 48), ch = gc(); return f ? res : -res; } const double pi=acos(-1); struct plx{ double x,y; plx(double _x=0,double _y=0):x(_x),y(_y){} friend inline plx operator +(const plx &a,const plx &b){ return plx(a.x+b.x,a.y+b.y); } friend inline plx operator -(const plx &a,const plx &b){ return plx(a.x-b.x,a.y-b.y); } friend inline plx operator /(const plx &a,const double &b){ return plx(a.x/b,a.y/b); } friend inline plx operator *(const plx &a,const plx &b){ return plx(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x); } }a[N],b[N]; inline void fft(plx f[],int lim,int kd){//kd表示在做正变换还是逆变换 for(int i=0;i<lim;i++)if(rev[i]>i)swap(f[i],f[rev[i]]); for(int mid=1;mid<lim;mid<<=1){ plx now=plx(cos(pi/mid),kd*sin(pi/mid)); for(int i=0;i<lim;i+=(mid<<1)){ plx w=plx(1,0); for(int j=0;j<mid;j++,w=w*now){ plx p0=f[i+j],p1=w*f[i+j+mid]; f[i+j]=p0+p1,f[i+j+mid]=p0-p1; } } } if(kd==-1)for(int i=0;i<lim;i++)f[i]=f[i]/lim; } int main() { int n = read(), m = read(); for (int i = 0; i <= n; i++) a[i].x = read(); for (int i = 0; i <= m; i++) b[i].x = read(); int lim=1,l=0; while (lim <= n + m) lim <<= 1, l++; for (int i = 0; i < lim; i++) rev[i] = ( rev[i >> 1] >> 1 ) | ( (i & 1) << (l - 1) ) ; // 在原序列中 i 与 i/2 的关系是 ： i可以看做是i/2的二进制上的每一位左移一位得来 // 那么在反转后的数组中就需要右移一位，同时特殊处理一下奇数 fft(a,lim, 1); fft(b,lim, 1); for (int i = 0; i <= lim; i++) a[i] = a[i] * b[i]; fft(a,lim, -1); for (int i = 0; i <= n + m; i++) printf("%d ", (int)(a[i].x + 0.5)); return 0; }