本地过了上面瓦+RE
查看原帖
本地过了上面瓦+RE
555381
zlttcl楼主2024/9/24 19:26
//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
const double Pi = acos(-1.0);
int n, m;
inline ll read(){
	ll x = 0, m = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') m = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * m;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		write(-x);
		return;
	}
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}
struct Code{
	double x, y;
	Code (double xx = 0, double yy = 0){x = xx, y = yy;}
}a[N], b[N];
inline Code operator + (Code a, Code b){
	return Code(a.x + b.x, a.y + b.y);
}
inline Code operator - (Code a, Code b){
	return Code(a.x - b.x, a.y - b.y);
}
inline Code operator * (Code a, Code b){
	return Code(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
inline void FFT(int L, Code *a, int op){
	if(L == 1) return;
	Code a1[L >> 1], a2[L >> 1];
	for(int i = 0; i <= L; i += 2) a1[i >> 1] = a[i], a2[i >> 1] = a[i + 1];
	FFT(L >> 1, a1, op), FFT(L >> 1, a2, op);
	Code W = Code(cos(2.0 * Pi / L), op * sin(2.0 * Pi / L)), w = Code(1, 0);
	for(int i = 0; i < (L >> 1); ++ i, w = w * W){
		a[i] = a1[i] + w * a2[i];
		a[i + (L >> 1)] = a1[i] - w * a2[i];
	}
}
signed main(){
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	n = read(), m = read();
	for(int i = 0; i <= n; ++ i) cin >> a[i].x;
	for(int i = 0; i <= m; ++ i) cin >> b[i].x;
	int L = 1;
	while(L <= n + m) L <<= 1;
	FFT(L, a, 1), FFT(L, b, 1);
	for(int i = 0; i <= L; ++ i) a[i] = a[i] * b[i];
	FFT(L, a, -1);
	for(int i = 0; i <= n + m; ++ i) write((int)(a[i].x / L + 0.5)), putchar(' '); 
	return 0;
}


开 -Wall 没有 Warning。

2024/9/24 19:26
加载中...