提交记录 3402


用户 题目 状态 得分 用时 内存 语言 代码长度
oscar 1002i. 【模板题】多项式乘法 Accepted 100 56.99 ms 6924 KB C++ 1.50 KB
提交时间 评测时间
2018-07-14 18:56:29 2020-07-31 21:16:54
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
const double pi=3.1415926535897932384626433832795;
struct c
{
	double r,i;
	inline c(){r=i=0.0;}
	inline c(const double a,const double b){r=a,i=b;}
	inline c operator+(const c &x)const{return c(r+x.r,i+x.i);}
	inline c operator+=(const c &x){return *this=*this+x;}
	inline c operator-(const c &x)const{return c(r-x.r,i-x.i);}
	inline c operator-=(const c &x){return *this=*this-x;}
	inline c operator*(const c &x)const{return c(r*x.r-i*x.i,r*x.i+i*x.r);}
	inline c operator*=(const c &x){return *this=*this*x;}
	inline c operator/=(const int x){r/=x,i/=x;return *this;}
	inline c conj(){return c(r,-i);}
}A[277777];
int r[277777],l=1;
int n,m;
inline void fft(c *a,int ty)
{
	for(int i=0;i<l;i++)i<r[i]?(void)(0):swap(a[i],a[r[i]]);
	for(int i=1;i<l;i<<=1)
	{
		c w(cos(pi/i),ty*sin(pi/i));
		for(int j=0;j<l;j+=i<<1)
		{
			c wn(1.0,0.0);
			for(int k=j;k<i+j;k++)
			{
				c t=a[i+k]*wn;
				a[i+k]=a[k]-t;
				a[k]+=t;
				wn*=w;
			}
		}
	}
}
int main()
{
	scanf("%d",&n);
	scanf("%d",&m);
	for(int i=0;i<=n;i++)scanf("%lf",&A[i].r);
	for(int i=0;i<=m;i++)scanf("%lf",&A[i].i);
	while(l<=n+m)l<<=1;
	for(int i=1;i<l;i<<=1)
		for(int j=0;j<i;j++)
			r[i+j]=r[j]+l/(i<<1);
	fft(A,1);
	A[l]=A[0];
	for(int i=0;i<=l-i;i++)
	{
		c t=(A[i]+A[l-i].conj())*c(0.0,1.0)*(A[i]-A[l-i].conj());t/=4;
		c t2=(A[l-i]+A[i].conj())*c(0.0,1.0)*(A[l-i]-A[i].conj());t2/=4;
		A[i]=t;A[l-i]=t2;
	}
	fft(A,-1);
	for(int i=0;i<=n+m;i++)printf("%d ",int(-A[i].r/l+0.5));
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #1479.34 us4 MB + 272 KBAcceptedScore: 0

Subtask #1 Testcase #256.809 ms6 MB + 700 KBAcceptedScore: 100

Subtask #1 Testcase #325.927 ms5 MB + 40 KBAcceptedScore: 0

Subtask #1 Testcase #425.978 ms5 MB + 28 KBAcceptedScore: 0

Subtask #1 Testcase #5479.68 us4 MB + 272 KBAcceptedScore: 0

Subtask #1 Testcase #6480.39 us4 MB + 272 KBAcceptedScore: 0

Subtask #1 Testcase #7472.24 us4 MB + 272 KBAcceptedScore: 0

Subtask #1 Testcase #850.49 ms6 MB + 432 KBAcceptedScore: 0

Subtask #1 Testcase #950.612 ms6 MB + 432 KBAcceptedScore: 0

Subtask #1 Testcase #1044.436 ms6 MB + 164 KBAcceptedScore: 0

Subtask #1 Testcase #1156.967 ms6 MB + 780 KBAcceptedScore: 0

Subtask #1 Testcase #1256.99 ms5 MB + 660 KBAcceptedScore: 0

Subtask #1 Testcase #13479.36 us4 MB + 272 KBAcceptedScore: 0


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