本文共 2144 字，大约阅读时间需要 7 分钟。

题目链接：https://www.oj.swust.edu.cn/problem/show/2540

代码：

#include<bits/stdc++.h>

using namespace std; const int FFT_MAXN = 1 << 18; const double pi = acos(-1.0); struct Complex {     double R, I;     inline Complex(double real = 0.0, double image = 0.0)     {         R = real, I = image;     }     inline Complex operator + (Complex const &b) const     {         return Complex(R + b.R, I + b.I);     }     inline Complex operator - (Complex const &b) const     {         return Complex(R - b.R, I - b.I);     }     inline Complex operator * (Complex const &b) const     {         return Complex(R * b.R - I * b.I, I * b.R + R * b.I);     } } Wn[FFT_MAXN + 1]; int bitrev[FFT_MAXN]; inline int getLength(int n, int m) {     n = n + m - 1;     int i = 1;     for(; i < n; i <<= 1);     return i; } void Change(Complex a[], int n) {     int d = 0;     while((1 << d)*n != FFT_MAXN)         d++;     for(int i = 0; i < n; i++)         if(i < (bitrev[i] >> d))             swap(a[i], a[bitrev[i] >> d]); } void FFT(Complex P[], int n, int op) {     Change(P, n);     for(int len = 2; len <= n; len <<= 1)     {         int m = len >> 1;         int del = FFT_MAXN / len * op;         for(int i = 0; i < n; i += len)         {             Complex *p = P + i, *q = P + i + m, *w = op == 1 ? Wn : Wn + FFT_MAXN;             for(int j = 0; j < m; j++, p++, q++, w += del)             {                 Complex ne = *q * *w;                 *q = *p - ne;                 *p = *p + ne;             }         }     }     if(op == -1)         for(int i = 0; i < n; i++)         {             P[i].R /= n;             P[i].I /= n;         } } void FFTInit() {     int L = 0;     while((1 << L) != FFT_MAXN)         L++;     bitrev[0] = 0;     for(int i = 1; i < FFT_MAXN; i++)         bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << (L - 1));     for(int i = 0; i <= FFT_MAXN; i++)         Wn[i] = Complex(cos(2 * pi / FFT_MAXN * i), sin(2 * pi / FFT_MAXN * i)); } Complex A[FFT_MAXN], B[FFT_MAXN]; int main() {     FFTInit();     int n, m;     scanf("%d%d", &n, &m);     int N = getLength(n, m);     for(int i = 0; i < N; i++)     {         if(i < n)         {             int x;             scanf("%d", &x);             A[i] = Complex(x, 0);         }         else A[i] = Complex();     }     for(int i = 0; i < N; i++)     {         if(i < m)         {             int y;             scanf("%d", &y);             B[i] = Complex(y, 0);         }         else B[i] = Complex();     }     FFT(A, N, 1);     FFT(B, N, 1);     for(int i = 0; i < N; i++)         A[i] = A[i] * B[i];     FFT(A, N, -1);     for(int i = 0; i <= n + m - 2; i++)     {         if(i == 0) printf("%d", (int)(A[i].R+0.5 ));         else printf(" %d", (int)(A[i].R+0.5));     }     printf("\n");     return 0; }

 

 

 

转载地址：http://vincf.baihongyu.com/