提交记录 17255


用户 题目 状态 得分 用时 内存 语言 代码长度
FYYY 1002i. 【模板题】多项式乘法 Accepted 100 50.355 ms 6696 KB C++ 1.60 KB
提交时间 评测时间
2022-01-09 09:37:44 2022-01-09 09:37:48
#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];
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){
		Complex Omiga={cos(Pi/i),sin(Pi/i)*Type};
		for(int j=0;j<Len;j+=(i<<1)){
			Complex Unit={1.0,0.0};
			for(int k=0;k<i;++k, Unit*=Omiga){
				Complex 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);
	for(int i=0;i<=n+m;++i) printf("%d ",(int)(0.5+F[i].Ima/(Len<<1)));
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #134.88 us44 KBAcceptedScore: 0

Subtask #1 Testcase #250.114 ms6 MB + 472 KBAcceptedScore: 100

Subtask #1 Testcase #322.874 ms2 MB + 836 KBAcceptedScore: 0

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

Subtask #1 Testcase #536.6 us44 KBAcceptedScore: 0

Subtask #1 Testcase #636.25 us44 KBAcceptedScore: 0

Subtask #1 Testcase #735.56 us44 KBAcceptedScore: 0

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

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

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

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

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

Subtask #1 Testcase #1334.02 us44 KBAcceptedScore: 0


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