提交记录 9017


用户 题目 状态 得分 用时 内存 语言 代码长度
shorn1 1002i. 【模板题】多项式乘法 Accepted 100 159.65 ms 49140 KB C++11 2.21 KB
提交时间 评测时间
2019-04-03 20:52:29 2020-08-01 01:29:20
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<utility>
#define lol long long
#define mp make_pair
#define ft first
#define sc second
using namespace std;
typedef pair<double,double> cpx;
const int M = 1008611;
const double _2pi = 2.0 * acos(-1);
char s1[M],s2[M];
stack<char> ans;
int n,m,l;

cpx operator +(const cpx &a,const cpx &b)
{
	return mp(a.ft + b.ft,a.sc + b.sc);
}

cpx operator -(const cpx &a,const cpx &b)
{
	return mp(a.ft - b.ft,a.sc - b.sc);
}

cpx operator *(const cpx &a,const cpx &b)
{
	return mp(a.ft * b.ft - a.sc * b.sc ,a.ft * b.sc + a.sc * b.ft);
}

cpx va[M],vb[M],vc[M];

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

void sread()
{
	int a;
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;i++)
	{
		a = read();
		va[i].ft = (double) a;
		va[i].sc = 0.0;
	}
	for(int i=0;i<=m;i++)
	{
		a = read();
		vb[i].ft = (double) a;
		vb[i].sc = 0.0;
	}
	if(n < m) 
	{
		swap(n,m);
		swap(va,vb); 
	} 	
	int t = n + m + 2;
	t <<= 1;
	for(l=1;l<t;l <<= 1);
}

void pre(int l,int r,cpx *v)
{
	if(l < r)
	{
		int mid = l + r >> 1;
		static cpx dl[M],dr[M];
		for(int i=l;i < r;i += 2)
		{
			dl[(i - l) >> 1] = v[i];
			dr[(i - l) >> 1] = v[i + 1];
		}
		memcpy(v + l,dl,(mid - l + 1) * sizeof(cpx));
		memcpy(v + mid + 1,dr,(r - mid) * sizeof(cpx));
		pre(l,mid,v);
		pre(mid + 1,r,v);
	}
}

void fft(cpx *v,int l,bool flg)
{
	const double pi2 = flg ? _2pi : -_2pi;
	for(int k = 2;k <=l ;k <<= 1)
	{
		cpx wn = mp(cos(pi2 / k),sin(pi2 / k));
		for(int i = 0;i < l; i += k)
		{
			cpx w = mp(1.0,0.0);
			for(int j = 0;j < k >> 1;j++)
			{
				cpx t1 = v[i + j],t2 = v[i + j + (k >> 1)] * w;
				v[i + j] = t1 + t2;
				v[i + j + (k >> 1)] = t1 - t2;
				w = w * wn;
			}
		}
	}
	if(!flg)
	{
		cpx inv = mp(1.0 / l,0.0);
		for(int i = 0; i < l;i++)
		{
			v[i] = v[i] * inv;
		}
	}
}

void print()
{
	for(int i=0;i<=n+m;i++)
	{
		printf("%d ",(int)(vc[i].ft + 0.5));
	}
}

int main()
{
	sread();
	pre(0,l-1,va);
	fft(va,l,true);
	pre(0,l-1,vb);
	fft(vb,l,true);
	for(int i=0;i<l;i++) vc[i] = va[i] * vb[i];
	pre(0,l-1,vc);
	fft(vc,l,false);
	print();
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #139.97 us64 KBAcceptedScore: 0

Subtask #1 Testcase #2159.414 ms33 MB + 492 KBAcceptedScore: 100

Subtask #1 Testcase #375.275 ms39 MB + 108 KBAcceptedScore: 0

Subtask #1 Testcase #470.746 ms16 MB + 332 KBAcceptedScore: 0

Subtask #1 Testcase #541.15 us64 KBAcceptedScore: 0

Subtask #1 Testcase #65.273 ms30 MB + 852 KBAcceptedScore: 0

Subtask #1 Testcase #740.88 us64 KBAcceptedScore: 0

Subtask #1 Testcase #8157.921 ms47 MB + 1012 KBAcceptedScore: 0

Subtask #1 Testcase #9154.375 ms33 MB + 224 KBAcceptedScore: 0

Subtask #1 Testcase #10148.785 ms32 MB + 980 KBAcceptedScore: 0

Subtask #1 Testcase #11159.376 ms33 MB + 572 KBAcceptedScore: 0

Subtask #1 Testcase #12159.65 ms32 MB + 452 KBAcceptedScore: 0

Subtask #1 Testcase #1339.32 us64 KBAcceptedScore: 0


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