P3803 【模板】多项式乘法（FFT） PS：注意输出为整形时要处理精度误差
#include<bits/stdc++.h> #define rint register int #define deb(x) cerr<<#x<<" = "<<(x)<<'\n'; using namespace std; typedef long long ll; const int maxn = 1e6 + 1e5; const double pi = acos(-1); int n, m, len, rev[maxn<<1]; struct cp { double x, y; cp(double _x=0, double _y=0) {x = _x, y = _y;} cp operator + (const cp &A) const {return cp(x+A.x, y+A.y);} cp operator - (const cp &A) const {return cp(x-A.x, y-A.y);} cp operator * (const cp &A) const {return cp(x*A.x-y*A.y, x*A.y+y*A.x);} } f[maxn<<1], p[maxn<<1]; void fft(cp *f, int inv) { for(int i=0; i<len; i++) if(i<rev[i]) swap(f[i], f[rev[i]]); for(int p=2; p<=len; p<<=1) { // 区间长度 int Len = p >> 1; // 待合并长度 cp wn(cos(2*pi/p), inv*sin(2*pi/p)); for(int k=0; k<len; k+=p) { // 起始点 cp w(1, 0); for(int i=k; i<k+Len; i++) { cp tmp = w * f[i+Len]; f[i+Len] = f[i] - tmp; f[i] = f[i] + tmp; w = w * wn; } } } if(inv == 1) return; for(int i=0; i<=n+m; i++) f[i].x = f[i].x / len + 0.49; } int main() { scanf("%d%d", &n, &m); for(int i=0; i<=n; i++) scanf("%lf", &f[i].x); for(int i=0; i<=m; i++) scanf("%lf", &p[i].x); for(len=1; len<=n+m; len<<=1); for(int i=0; i<len; i++) rev[i] = (rev[i>>1]>>1) | ((i&1) ? len>>1 : 0); fft(f, 1), fft(p, 1); for(int i=0; i<len; i++) f[i] = f[i] * p[i]; fft(f, -1); for(int i=0; i<=n+m; i++) printf("%d ", (int)f[i].x); }