提交记录 17261


用户 题目 状态 得分 用时 内存 语言 代码长度
LinZhengyu 1002i. 【模板题】多项式乘法 Accepted 100 55.963 ms 4632 KB C++ 1.31 KB
提交时间 评测时间
2022-01-11 20:36:04 2022-01-11 20:36:07
#include<cstdio>
typedef unsigned ui;
typedef unsigned long long ull;
const ui N=1048576u,M=2097152u,P=998244353u,G=3u;
ui n,m,f[M+5u],g[M+5u];

ui og[M+5u];
inline ui upb(ui x){x|=x>>1u,x|=x>>2u,x|=x>>4u,x|=x>>8u,x|=x>>16u;return x+1u;}
inline void rev(ui*l,ui*r){ui z;for(;l<r;z=*l,*l++=*r,*r--=z);}
inline ui ksm(ui x,ui y){ui z=1u;for(;y;x=(ull)x*x%P,y>>=1u)if(y&1u)z=(ull)z*x%P;return z;}
inline void Tii(ui x)
{
	if(x==1)return;
	og[x>>1]=1;
	for(ui i=(x>>1)+1,e=ksm(G,(P-1)/x);i<x;++i)
		og[i]=1ll*og[i-1]*e%P;
	for(ui i=(x>>1)-1;i;--i)og[i]=og[i<<1];
}
inline void DIF(ui*tf,ui x)
{
	for(ui i=x>>1u;i;i>>=1u)
		for(ui j=0u;j<x;j+=i<<1u)
			for(ui k=0u,z;k<i;++k)
			{
				z=(ull)(tf[j|k]+P-tf[j|i|k])*og[i|k]%P;
				(tf[j|k]+=tf[j|i|k])%=P,tf[j|i|k]=z;
			}
}
inline void DFT(ui*tf,ui x)
{
	for(ui i=1u;i<x;i<<=1u)
		for(ui j=0u;j<x;j+=i<<1u)
			for(ui k=0u,z;k<i;++k)
			{
				z=(ull)og[i|k]*tf[j|i|k]%P;
				tf[j|i|k]=(tf[j|k]+P-z)%P,(tf[j|k]+=z)%=P;
			}
	for(ui i=0u,z=P-(P-1u)/x;i<x;++i)
		tf[i]=(ull)tf[i]*z%P;
	rev(tf+1u,tf+x-1);
}

int main()
{
	scanf("%u%u",&m,&n);
	for(ui i=0u;i<=m;++i)scanf("%u",&f[i]);
	for(ui i=0u;i<=n;++i)scanf("%u",&g[i]);
	
	n+=m,m=upb(n);
	Tii(m);
	DIF(f,m),DIF(g,m);
	for(ui i=0u;i<m;++i)
		f[i]=(ull)f[i]*g[i]%P;
	DFT(f,m);
	
	for(ui i=0u;i<=n;++i)
		printf("%u ",f[i]);
	puts("");
	
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #110.03 us28 KBAcceptedScore: 0

Subtask #1 Testcase #255.181 ms4 MB + 456 KBAcceptedScore: 0

Subtask #1 Testcase #325.389 ms1 MB + 820 KBAcceptedScore: 100

Subtask #1 Testcase #425.38 ms1 MB + 808 KBAcceptedScore: 0

Subtask #1 Testcase #510.58 us28 KBAcceptedScore: 0

Subtask #1 Testcase #610.29 us28 KBAcceptedScore: 0

Subtask #1 Testcase #710.14 us28 KBAcceptedScore: 0

Subtask #1 Testcase #849.487 ms4 MB + 188 KBAcceptedScore: 0

Subtask #1 Testcase #949.514 ms4 MB + 188 KBAcceptedScore: 0

Subtask #1 Testcase #1043.785 ms3 MB + 944 KBAcceptedScore: 0

Subtask #1 Testcase #1155.484 ms4 MB + 536 KBAcceptedScore: 0

Subtask #1 Testcase #1255.963 ms3 MB + 416 KBAcceptedScore: 0

Subtask #1 Testcase #139.08 us28 KBAcceptedScore: 0


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