提交记录 5342


用户 题目 状态 得分 用时 内存 语言 代码长度
hytzongxuan 1002i. 【模板题】多项式乘法 Accepted 100 98.42 ms 133652 KB C++ 2.08 KB
提交时间 评测时间
2018-08-18 20:36:40 2020-08-01 00:16:03
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
 
using namespace std;
const int MAXN = 2097152 + 10;
const double PI = acos(-1.0);

struct complex{
	double x, y;
	complex (double xx=0, double yy=0){x=xx, y=yy;}
};

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);}

complex omega[MAXN], omegaInverse[MAXN];

int place[MAXN];

inline void init(int n){
	int k = 0;
	while((1 << k) < n)
		k++;
	
	for(register int i=0; i<n; i++){
		for(register int j=0; j<k; j++){
			if(i & (1 << j))
				place[i] |= (1 << (k - j - 1));
		}
	}
		
	double single = 2 * PI / n;
	
	for(register int i=0; i<n; i++){
		omega[i] = complex(cos(single*i), sin(single*i));
		omegaInverse[i] = complex(omega[i].x, -omega[i].y);
	}
}

inline void transform(complex *a, int n, complex *omega){
	for(register int i=0; i<n; i++){
		if(i < place[i])
			swap(a[i], a[place[i]]);
	}
	
	for(register int range=2; range <=n; range <<= 1){
		int mid = range >> 1;
		int k = n / range;
		
		for(register complex *p = a; p != a + n; p += range){
			for(register int i=0; i<mid; i++){
				int tmp = mid + i;
				
				complex t = omega[k * i] * p[tmp];
				p[tmp] = p[i] - t;
				p[i] = p[i] + t;
			}
		}
	}
}

inline int read(){
	int x = 0;
	char ch = getchar();
	
	while(ch < '0' || ch > '9')
		ch = getchar();
	
	while('0' <= ch && ch <= '9'){
		x = x*10 + ch - '0';
		ch = getchar();
	}
	
	return x;
}

int n1, n2;
complex c1[MAXN], c2[MAXN];
int ans[MAXN];

int main(){

	n1 = read();
	n2 = read();
	
	n1++;
	n2++;
	
	int n = 1;
	
	while(n < n1 + n2)
		n <<= 1;
	
	for(register int i=0; i<n1; i++)
		c1[i].x = read();
	
	for(register int i=0; i<n2; i++)
		c2[i].x = read();
	
		
	init(n);
	
	transform(c1, n, omega);
	transform(c2, n, omega);
	
	for(register int i=0; i<n; ++i)
		c1[i] = c1[i] * c2[i];
	
	transform(c1, n, omegaInverse);
	
	for(register int i=0; i<n1+n2-1; i++){
		printf("%d ", (int)floor(c1[i].x/n + 0.5));
	}
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #114.861 ms128 MB + 24 KBAcceptedScore: 0

Subtask #1 Testcase #296.787 ms130 MB + 452 KBAcceptedScore: 0

Subtask #1 Testcase #351.309 ms128 MB + 816 KBAcceptedScore: 100

Subtask #1 Testcase #451.304 ms128 MB + 804 KBAcceptedScore: 0

Subtask #1 Testcase #515.034 ms128 MB + 24 KBAcceptedScore: 0

Subtask #1 Testcase #614.266 ms128 MB + 24 KBAcceptedScore: 0

Subtask #1 Testcase #714.272 ms128 MB + 24 KBAcceptedScore: 0

Subtask #1 Testcase #891.333 ms130 MB + 184 KBAcceptedScore: 0

Subtask #1 Testcase #992.075 ms130 MB + 184 KBAcceptedScore: 0

Subtask #1 Testcase #1086.347 ms129 MB + 940 KBAcceptedScore: 0

Subtask #1 Testcase #1197.213 ms130 MB + 532 KBAcceptedScore: 0

Subtask #1 Testcase #1298.42 ms129 MB + 412 KBAcceptedScore: 0

Subtask #1 Testcase #1314.266 ms128 MB + 24 KBAcceptedScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-29 13:00:19 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用