快速傅里叶变换(FFT)
#include <bits/stdc++.h>
using namespace std;
const int N=4e6; //2^22=4194304
const double PI=acos(-1.0);
typedef complex<double> Complex;
double A[N], B[N], C[N]; // FFT加速卷积，输入：a[0..na], b[0..nb]，输出：c[0..na+nb]
void Mul(double *a, double *b, double *c, int na, int nb) {int len = 1;while (len < na + nb - 1) len <<= 1; // 补齐到 2 的幂static Complex A[1 << 22], B[1 << 22]; // 注意：临时数组大小需根据实际最大len调整for (int i = 0; i < na; i++) A[i] = Complex(a[i], 0);fill(A + na, A + len, Complex(0, 0));for (int i = 0; i < nb; i++) B[i] = Complex(b[i], 0);fill(B + nb, B + len, Complex(0, 0));vector<int> rev(len); // 位逆序置换数组for (int i = 0; i < len; i++)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (len >> 1) : 0);auto fft = [&](Complex *a, int type) { // FFT 变换（type=1 为正变换，-1 为逆变换）for (int i = 0; i < len; i++)if (i < rev[i]) swap(a[i], a[rev[i]]);for (int mid = 1; mid < len; mid <<= 1) {Complex wn(cos(PI / mid), type * sin(PI / mid)); // 单位根for (int i = 0; i < len; i += (mid << 1)) {Complex w(1, 0);for (int j = 0; j < mid; j++) {Complex x = a[i + j], y = w * a[i + j + mid];a[i + j] = x + y;a[i + j + mid] = x - y;w *= wn;}}}if (type == -1) {for (int i = 0; i < len; i++) a[i] /= len;}};fft(A, 1); fft(B, 1);for (int i = 0; i < len; i++) A[i] *= B[i];fft(A, -1);for (int i = 0; i < na + nb - 1; i++) c[i] = A[i].real(); // 取实部
}
int main() {int n, m; scanf("%d%d", &n, &m);for(int i=0; i <= n; i++) scanf("%lf", &A[i]);for(int i=0; i <= m; i++) scanf("%lf", &B[i]);Mul(A, B, C, n+1, m+1);for(int i=0; i <= n+m; i++) printf("%d ", (int)(C[i] + 0.5));return 0;
}
快速数论变换(NTT)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e6;
const int P=998244353;
int A[N], B[N], C[N];
int qpow(int a, int b) {int ans=1;for(; b; a=a*a%P, b>>=1)if(b&1) ans=ans*a%P;return ans;
}
// NTT加速 输入：a[0..na], b[0..nb] 输出：c[0..na+nb]
void Mul(int *a, int *b, int *c, int na, int nb) {int len=1;while(len < na+nb-1) len<<=1; // 补齐到 2 的幂static int A[N], B[N]; // 临时数组copy(a, a+na, A); fill(A+na, A+len, 0);copy(b, b+nb, B); fill(B+nb, B+len, 0);vector<int> rev(len); // 位逆序置换数组for (int i=0; i < len; i++)rev[i]=(rev[i>>1]>>1)|((i&1) ? (len>>1) : 0);auto ntt=[&](int *a, int type) {//NTT lambda捕获rev和lenfor(int i=0; i < len; i++)if(i < rev[i]) swap(a[i], a[rev[i]]);for(int mid=1; mid < len; mid <<= 1) {int wn=qpow(3, (P-1)/(mid<<1)); //原根取3 if(type == -1) wn=qpow(wn, P-2); //逆变换用逆元for(int i=0; i < len; i+=(mid<<1)) {int w=1;for(int j=0; j < mid; j++) {int x=a[i+j], y=w*a[i+j+mid]%P;a[i+j]=(x+y)%P;a[i+j+mid]=(x-y+P)%P;w=w*wn%P;}}}if(type == -1) {int inv_len=qpow(len, P-2);for(int i=0; i < len; i++) a[i]=a[i]*inv_len%P;}};ntt(A, 1); ntt(B, 1);for(int i=0; i < len; i++) A[i]=A[i]*B[i]%P;ntt(A, -1);for(int i=0; i < na+nb-1; i++) c[i]=A[i];
}signed main() {int n, m;cin >> n >> m;for(int i=0; i <= n; i++) cin >> A[i];for(int i=0; i <= m; i++) cin >> B[i];Mul(A, B, C, n+1, m+1);for(int i=0; i <= n+m; i++) cout << C[i] << ' ';return 0;
}