提交记录 6336


用户 题目 状态 得分 用时 内存 语言 代码长度
Moon 1002i. 【模板题】多项式乘法 Accepted 100 74.487 ms 5656 KB C++ 1.66 KB
提交时间 评测时间
2018-10-06 07:47:18 2020-08-01 00:42:21
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <limits>
#include <map>
#include <vector>
#include <queue> 
#define LL int
#define ft first
#define sd second
#define mp(x,y) make_pair(x,y)
#define db double
//#define int LL
using namespace std;
const int N   = 1<<21;
const int mod = 1004535809;
const int INF =numeric_limits<int >::max();
const db Pi=acos(-1.);
#define rep(i,x,y) for (int i=x;i<=y;++i)
#define rr(i,x,y) for (int i=x;i<y;++i)
void read(int &x)
{
	x=0;
	char ch=getchar();
	int f=1;
	while (!isdigit(ch)) (ch=='-'?f=-1:0),ch=getchar();
	while ( isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	x*=f;
}

int n,m,A[N],B[N];
int C[N];

int qsm(int a,int b)
{
	int tmp=1;
	while (b)
	{
		if (b&1) tmp=1ll*tmp*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return tmp;
}

int rev[N*4];
const int yg=3;
void NTT(int *a,int n,int f)
{
	rr(i,0,n) if (i>rev[i]) swap(a[i],a[rev[i]]);
	for (int i=1;i<n;i<<=1)
	{
		int wn=qsm(yg,(mod-1)/(i<<1)),x,y;
		for (int j=0;j<n;j+=(i<<1))
		{
			for (int w=1,k=0;k<i;++k,w=1ll*wn*w%mod)
			{
				x=a[j+k];
				y=1ll*a[i+j+k]*w%mod;
				a[j+k]=(x+y)%mod;
				a[i+j+k]=(x-y+mod)%mod;
			}
		}
	}
	if (f==1) return;
	reverse(a+1,a+n);
	int inv=qsm(n,mod-2);
	rr(i,0,n) a[i]=1ll*a[i]*inv%mod;
}

void cal(int *a,int * b,int n,int m,int *c)
{
	int R=n+m,L=1,g=0;
	for (;L<=R;L<<=1,++g);
	rr(i,0,L) rev[i]=(rev[i>>1]>>1) | ((i&1)<<g-1);
	NTT(A,L,1);NTT(B,L,1);
	rr(i,0,L) C[i]=1ll*A[i]*B[i]%mod;
	NTT(C,L,-1);
}

signed main()
{
	///freopen("data.txt","r",stdin);
	//freopen("Moon.txt","w" ,stdout);
	read(n);read(m);
	rep(i,0,n) read(A[i]);
	rep(i,0,m) read(B[i]);
	cal(A,B,n,m,C);
	n+=m;
	rep(i,0,n) printf("%d ",C[i]);
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #18.86 us28 KBAcceptedScore: 0

Subtask #1 Testcase #273.896 ms5 MB + 456 KBAcceptedScore: 100

Subtask #1 Testcase #333.967 ms2 MB + 308 KBAcceptedScore: 0

Subtask #1 Testcase #433.973 ms2 MB + 296 KBAcceptedScore: 0

Subtask #1 Testcase #59.67 us28 KBAcceptedScore: 0

Subtask #1 Testcase #610.13 us28 KBAcceptedScore: 0

Subtask #1 Testcase #78.47 us28 KBAcceptedScore: 0

Subtask #1 Testcase #868.841 ms5 MB + 188 KBAcceptedScore: 0

Subtask #1 Testcase #968.665 ms5 MB + 188 KBAcceptedScore: 0

Subtask #1 Testcase #1063.479 ms4 MB + 944 KBAcceptedScore: 0

Subtask #1 Testcase #1174.16 ms5 MB + 536 KBAcceptedScore: 0

Subtask #1 Testcase #1274.487 ms4 MB + 416 KBAcceptedScore: 0

Subtask #1 Testcase #137.78 us28 KBAcceptedScore: 0


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