RT

不知道为什么会比别人的代码慢2-3倍，感觉自己写的挺优的…

#include<cstdio>
#include<complex>
#include<cmath>
#include<iostream>
#include<ctime>
#include<algorithm>
#define C complex 
const int _ = 4e6 + 10;
inline int read()
{
    char c = getchar(); int sign = 1; int x = 0;
    while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); }
    while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); }
    return x * sign;
}
struct complex {
    double x, y;
    complex (double x = 0, double y = 0): x(x), y(y) {}
    void real(int _x) { x = _x; }
};
complex operator+(complex a,complex b) { return complex(a.x + b.x, a.y + b.y); }
complex operator-(complex a,complex b) { return complex(a.x - b.x, a.y - b.y); }
complex operator*(complex a,complex b) { return complex(a.x * b.x - a.y * b.y, a.x * b.y + a.y*b.x); }

C A[_], B[_], eps[_], ieps[_];
int rev[_];
void init(int n){
	double PIN = 3.141592653 / n;
	for(int i = 0;i <= n;i++) eps[i].y = sin(2 * PIN * i), eps[i].x = cos(2 * PIN * i);// eps[i] = C(std::polar(1.0, 2 * PIN * i).real(),std::polar(1.0, 2 * PIN * i).imag()) ;
	eps[0] = ieps[0] = 1;
	for(int i = 0;i <= n;i++)ieps[i] = eps[n - i];
	for(int i = 0, j = 0;i < n;i++){
		rev[i] = j;
		for(int l = n >> 1; (j ^= l) < l;l >>= 1);
	}
}



void FFT(int n, C *x, C *w){
	
	for(int i = 0;i < n;i++){
		if(i < rev[i]) {
			C t = x[i]; x[i] = x[rev[i]]; x[rev[i]] = t;
		}
	}
	for(int i = 2;i <= n;i <<= 1){
		int l = i >> 1, d = n / i;
		for(int j = 0;j < n;j += i){
			for(int k = 0;k < l;k++){
				C t = w[d * k] * x[j + k + l];
				x[j + k + l] = x[j + k] - t;
				x[j + k]     = x[j + k] + t;
			}
		}
	}
}
int main()
{
	int n, m; n = read(), m = read();
	for(int i = 0;i <= n;i++) A[i].real(read());
	for(int i = 0;i <= m;i++) B[i].real(read());
	int len = 1;
	while(len < (n + m + 1)) len <<= 1; // std::cerr << len << std::endl;
	for(int i = n + 1;i < len;i++) A[i] = C(0, 0);
	for(int i = m + 1;i < len;i++) B[i] = C(0, 0);
	init(len);
	FFT(len, A, eps);
	FFT(len, B, eps);
	
	for(int i = 0;i < len;i++) A[i] = A[i] * B[i];
	
	FFT(len, A, ieps);
	for(int i = 0;i < n + m + 1;i++) printf("%d ", int(A[i].x / len + 0.5));
	return 0;
 }