提交记录 8778


用户 题目 状态 得分 用时 内存 语言 代码长度
xenonex 1002i. 【模板题】多项式乘法 Accepted 100 56.869 ms 5644 KB C++ 1.23 KB
提交时间 评测时间
2019-03-12 08:52:56 2020-08-01 01:24:25
#include<cstdio>
#include<cstring>
#define mod 998244353
typedef long long LL;
int W[2][262144],_i[19];
inline int fmo(int a,int b)
{
	return (LL)a*b%mod;
}
inline int ksm(LL a,LL b){int r=1;for(;b;a=fmo(a,a),b>>=1)if(b&1)r=fmo(r,a);return r;}
void NTT_Init()
{
	int i,j,t,*x;
	for(i=1;i<262144;i<<=1)
	{
		W[0][i] = 1, t = ksm(3,(mod-1)/i/2);
		for(j=1;j<i;j++)W[0][i+j] = fmo(W[0][i+j-1],t);
		W[1][i] = 1, t = ksm(332748118,(mod-1)/i/2);
		for(j=1;j<i;j++)W[1][i+j] = fmo(W[1][i+j-1],t);
	}
	for(_i[0]=i=1;i<19;i++)_i[i] = fmo(_i[i-1],499122177);
}
void NTT(int *f,int len,int sign)
{
	int i,j,k,*w,*p,*q,t;sign=sign==-1;
	for(i=j=0;i<len;i++){if(i<j)f[i]^=f[j]^=f[i]^=f[j];for(k=len>>1;(j^=k)<k;k>>=1);}
	for(i=1;i<len;i<<=1)for(j=0;j<len;j+=i<<1)for(w=W[sign]+i,q=(p=f+j)+i,k=0;k<i;k++)
		{t=fmo(*q,*w++);if((*q=*p-t)<0){*q+=mod;}if((*p+=t)>=mod){*p-=mod;}p++,q++;}
	if(sign)for(k=_i[__builtin_ctz(len)],i=0;i<len;i++)f[i] = fmo(k,f[i]);
}
int a[262144],b[262144];
int main()
{
	int n,m,i,l;
	NTT_Init();
	scanf("%d%d",&n,&m);
	for(i=0;i<=n;i++)scanf("%d",a+i);
	for(i=0;i<=m;i++)scanf("%d",b+i);
	n = n+m+1;
	for(l=1;l<n;l<<=1);
	NTT(a,l,1), NTT(b,l,1);
	for(i=0;i<l;i++)a[i] = fmo(a[i],b[i]);
	NTT(a,l,-1);
	for(i=0;i<n;i++)printf("%d ",a[i]);
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #12.737 ms2 MB + 24 KBAcceptedScore: 0

Subtask #1 Testcase #256.556 ms5 MB + 444 KBAcceptedScore: 100

Subtask #1 Testcase #327.313 ms3 MB + 304 KBAcceptedScore: 0

Subtask #1 Testcase #427.341 ms3 MB + 292 KBAcceptedScore: 0

Subtask #1 Testcase #52.738 ms2 MB + 24 KBAcceptedScore: 0

Subtask #1 Testcase #62.736 ms2 MB + 24 KBAcceptedScore: 0

Subtask #1 Testcase #72.736 ms2 MB + 24 KBAcceptedScore: 0

Subtask #1 Testcase #850.718 ms5 MB + 176 KBAcceptedScore: 0

Subtask #1 Testcase #950.948 ms5 MB + 176 KBAcceptedScore: 0

Subtask #1 Testcase #1045.183 ms4 MB + 932 KBAcceptedScore: 0

Subtask #1 Testcase #1156.788 ms5 MB + 524 KBAcceptedScore: 0

Subtask #1 Testcase #1256.869 ms4 MB + 404 KBAcceptedScore: 0

Subtask #1 Testcase #132.736 ms2 MB + 24 KBAcceptedScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2024-12-05 10:46:07 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠