【FFT】洛谷 P3803 【模板】多项式乘法（FFT）

题链

套了题解区的板子

 #include <bits/stdc++.h>
using namespace std;
#define LL long long
#define MS 1000009

int n,m;
int p1[MS], p2[MS];
double ac[MS<<1];

// 洛谷 P3803 【模板】多项式乘法（FFT）
// MS = 1e6 
// time: max( 800ms ) 
// ========================================================================================
typedef complex<double> comp;
const double PI = acos(-1);
const int N = (1<<21)+10; // 长度为原长度向上的2^n, 再乘 2  
int lim, r[N];
comp a[N], b[N];

void fft(comp * a, int type) {
	for(int i = 0; i < lim; i ++)
		if(i < r[i]) swap(a[i], a[r[i]]);
	for(int i = 1; i < lim; i <<= 1) {
		comp x(cos(PI / i), type * sin(PI / i));
		for(int j = 0; j < lim; j += (i << 1)) {
			comp y(1, 0);
			for(int k = 0; k < i; k ++, y *= x) {
				comp p = a[j + k], q = y * a[j + k + i];
				a[j + k] = p + q; a[j + k + i] = p - q;
			}
		}
	}
}
// 多项式 c1 [0,n]; 多项式 c2 [0,m];
// 返回结果 c  
void get(int *c1, int n, int *c2, int m, double *c){ 
	for(int i = 0; i <= n; i ++) a[i] = c1[i];
	for(int i = 0; i <= m; i ++) b[i] = c2[i];
	int l = 0;
	for(lim = 1; lim <= n + m; lim <<= 1) ++ l;
	for(int i = 0; i < lim; i ++)
		r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
		
	fft(a, 1), fft(b, 1);
	for(int i = 0; i <= lim; i ++) a[i] *= b[i];
	fft(a, -1);
	
	for(int i = 0; i <= n + m; i ++) c[i] = (int)(0.5 + a[i].real() / lim);
}
// ========================================================================================


int main() {
	// 两多项式乘积的系数 
	scanf("%d %d",&n,&m);
	for(int i = 0; i <= n; i ++) scanf("%d",&p1[i]);
	for(int i = 0; i <= m; i ++) scanf("%d",&p2[i]);
	get(p1, n, p2, m, ac);  
	for(int i=0;i<=n+m;i++) printf("%lld ",(LL)ac[i]);
	
	return 0;
}