提交记录 17263


用户 题目 状态 得分 用时 内存 语言 代码长度
LinZhengyu 1002i. 【模板题】多项式乘法 Accepted 100 58.023 ms 4632 KB C++ 1.34 KB
提交时间 评测时间
2022-01-11 20:37:31 2022-01-11 20:37:34
#include<cstdio>
#include<algorithm>
#include<cassert>
#include<ctime>
const int N=1<<20,M=1<<21,P=998244353,G=3;

int n,m,f[M+5],g[M+5],h[M+5],og[M+5];

inline int ksm(int x,int y){int z=1;for(;y;x=1ll*x*x%P,y>>=1)if(y&1)z=1ll*z*x%P;return z;}
inline int inv(int x){return ksm(x,P-2);}
inline int upb(int x){--x,x|=x>>1,x|=x>>2,x|=x>>4,x|=x>>8,x|=x>>16;return x+1;}
inline void ntt_init(int l)
{
	if(l>1)og[1]=1;
	for(int i=2;i<l;i<<=1)
	{
		int e=ksm(G,(P-1)/(i*2));
		for(int j=i;j<i*2;j+=2)og[j]=og[j>>1],og[j|1]=1ll*og[j]*e%P;
	}
}
inline void dif(int a[],int l)
{
	for(int i=l>>1;i;i>>=1)for(int j=0;j<l;j+=i*2)for(int k=0;k<i;++k)
	{
		int x=a[j|k],y=a[j|i|k];
		a[j|k]=(x+y)%P,a[j|i|k]=1ll*(x+P-y)*og[i|k]%P;
	}
}
inline void idft(int a[],int l)
{
	for(int i=1;i<l;i<<=1)for(int j=0;j<l;j+=i*2)for(int k=0;k<i;++k)
	{
		int x=a[j|k],y=1ll*a[j|i|k]*og[i|k]%P;
		a[j|k]=(x+y)%P,a[j|i|k]=(x+P-y)%P;
	}
	for(int i=0,z=inv(l);i<l;++i)a[i]=1ll*a[i]*z%P;
	for(int i=1;i<l-i;++i)std::swap(a[i],a[l-i]); 
}

int main()
{
//	freopen("ntt.in","r",stdin);
//	freopen("ntt.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;++i)scanf("%d",&f[i]);
	for(int i=0;i<=m;++i)scanf("%d",&g[i]);
	
	int l=upb(n+m+1);
	ntt_init(l);
	dif(f,l),dif(g,l);
	for(int i=0;i<l;++i)f[i]=1ll*f[i]*g[i]%P;
	idft(f,l);
	
	for(int i=0;i<=n+m;++i)printf("%d ",f[i]);
	puts("");
	
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #110.17 us28 KBAcceptedScore: 0

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

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

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

Subtask #1 Testcase #511.14 us28 KBAcceptedScore: 0

Subtask #1 Testcase #611.06 us28 KBAcceptedScore: 0

Subtask #1 Testcase #710.28 us28 KBAcceptedScore: 0

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

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

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

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

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

Subtask #1 Testcase #139.46 us28 KBAcceptedScore: 0


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