提交记录 17256


用户 题目 状态 得分 用时 内存 语言 代码长度
FYYY 1002i. 【模板题】多项式乘法 Accepted 100 55.29 ms 6696 KB C++ 1.60 KB
提交时间 评测时间
2022-01-09 09:42:18 2022-01-09 09:42:22
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int read(){
	int n=0; char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') n=n*10+(c^48), c=getchar();
	return n;
}

const int Mx=3e5;
const double Pi=acos(-1);
struct Complex{
	double Real,Ima;
	Complex operator + (const Complex& a) const { return (Complex){Real+a.Real,Ima+a.Ima};}
	Complex operator - (const Complex& a) const { return (Complex){Real-a.Real,Ima-a.Ima};}
	Complex operator * (const Complex& a) const { return (Complex){Real*a.Real-Ima*a.Ima,Real*a.Ima+Ima*a.Real};}
	Complex operator += (const Complex& a) { return (*this)=(Complex){Real+a.Real,Ima+a.Ima};}
	Complex operator -= (const Complex& a) { return (*this)=(Complex){Real-a.Real,Ima-a.Ima};}
	Complex operator *= (const Complex& a) { return (*this)=(Complex){Real*a.Real-Ima*a.Ima,Real*a.Ima+Ima*a.Real};}
}F[Mx],Omiga,Unit,A1,A2;
int Rfl[Mx];
void FFT(Complex A[],int Len,int Type){
	for(int i=0;i<Len;++i) if(i<Rfl[i]) swap(F[i],F[Rfl[i]]);
	for(int i=1;i<Len;i<<=1){
		Omiga={cos(Pi/i),sin(Pi/i)*Type};
		for(int j=0;j<Len;j+=(i<<1)){
			Unit={1.0,0.0};
			for(int k=0;k<i;++k, Unit*=Omiga){
				A1=A[k+j], A2=A[k+j+i]*Unit, A[k+j]=A1+A2, A[k+j+i]=A1-A2;
			}
		}
	}
}
int main(){
	int n=read(),m=read();
	for(int i=0;i<=n;++i) F[i].Real=read();
	for(int i=0;i<=m;++i) F[i].Ima=read();
	int Len=1,pw=0;
	while(Len<=n+m) Len<<=1, ++pw;
	for(int i=1;i<Len;++i) Rfl[i]=(i&1)?(Rfl[i-1]+(1<<(pw-1))):Rfl[i>>1]>>1;
	FFT(F,Len,1);
	for(int i=0;i<Len;++i) F[i]*=F[i];
	FFT(F,Len,-1);
	n+=m;
	Len<<=1;
	for(int i=0;i<=n;++i) printf("%d ",(int)(0.5+F[i].Ima/Len));
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #135.22 us44 KBAcceptedScore: 0

Subtask #1 Testcase #255.079 ms6 MB + 472 KBAcceptedScore: 0

Subtask #1 Testcase #325.133 ms2 MB + 836 KBAcceptedScore: 100

Subtask #1 Testcase #425.162 ms2 MB + 824 KBAcceptedScore: 0

Subtask #1 Testcase #538.67 us44 KBAcceptedScore: 0

Subtask #1 Testcase #636.05 us44 KBAcceptedScore: 0

Subtask #1 Testcase #736.3 us44 KBAcceptedScore: 0

Subtask #1 Testcase #849.614 ms6 MB + 204 KBAcceptedScore: 0

Subtask #1 Testcase #949.639 ms6 MB + 204 KBAcceptedScore: 0

Subtask #1 Testcase #1044.23 ms5 MB + 960 KBAcceptedScore: 0

Subtask #1 Testcase #1155.29 ms6 MB + 552 KBAcceptedScore: 0

Subtask #1 Testcase #1255.263 ms5 MB + 432 KBAcceptedScore: 0

Subtask #1 Testcase #1334.13 us44 KBAcceptedScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2022-01-29 06:49:33 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用