提交记录 22550


用户 题目 状态 得分 用时 内存 语言 代码长度
Prean 1002. 测测你的多项式乘法 Compile Error 0 0 ns 0 KB C++17 1.81 KB
提交时间 评测时间
2024-09-26 23:08:29 2024-09-26 23:08:30
#include<cstdio>
#include<cctype>
#define IMP(n,act) for(int lim=(n),i=0;i^lim;++i)act
const int M=5e6+5,mod=998244353;
int buf[M<<1],*w[25];
int n,m,f[M],g[M];
inline void swap(int&a,int&b){
	int c=a;a=b;b=c;
}
inline int Getlen(const int&n){
	int len(0);while((1<<len)<n)++len;return len;
}
inline int Add(const int&a,const int&b){
	return a+b>=mod?a+b-mod:a+b;
}
inline int Del(const int&a,const int&b){
	return b>a?a-b+mod:a-b;
}
inline int pow(int a,int b=mod-2){
	int ans(1);for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;return ans;
}
inline void init(const int&n){
	const int&m=Getlen(n);int*W=buf;w[m]=W;W+=1<<m;w[m][0]=1;w[m][1]=pow(3,mod-1>>m+1);
	for(int i=2;i^(1<<m);++i)w[m][i]=1ll*w[m][i-1]*w[m][1]%mod;
	for(int k=m-1;k>=0&&(w[k]=W,W+=1<<k);--k)IMP(1<<k,w[k][i]=w[k+1][i<<1]);
}
inline void DFT(int*f,const int&M){
	const int&n=1<<M;
	for(int d=M-1,len=n>>1;d>=0;--d,len>>=1){
		for(int k=0;k^n;k+=len<<1){
			int*fl=f+(k),*fr=f+(k|len),*W=w[d],x,y;
			IMP(len,(x=*fl,y=*fr)),*fl++=Add(x,y),*fr++=1ll**W++*Del(x,y)%mod;
		}
	}
}
inline void IDFT(int*f,const int&M){
	const int&n=1<<M;
	for(int d=0,len=1;d<M;++d,len<<=1){
		for(int k=0;k^n;k+=len<<1){
			int*fl=f+(k),*fr=f+(k|len),*W=w[d],x,y;
			IMP(len,(x=*fl,y=1ll**W++**fr%mod)),*fl++=Add(x,y),*fr++=Del(x,y);
		}
	}
	const int&k=pow(n);IMP(n,f[i]=1ll*f[i]*k%mod);for(int i=1;(i<<1)<n;++i)swap(f[i],f[n-i]);
}
inline int read(){
	int n(0);char s;while(!isdigit(s=getchar()));while(n=n*10+(s^48),isdigit(s=getchar()));return n;
}
inline void write(int n){
	static char s[20];int top(0);while(s[++top]=n%10^48,n/=10);while(putchar(s[top]),--top);
}
int main(){
	int n=read()+1,m=read()+1;init(n+m-1);IMP(n,f[i]=read());IMP(m,g[i]=read());
	const int&len=Getlen(n+m-1);DFT(f,len);DFT(g,len);IMP(1<<len,f[i]=1ll*f[i]*g[i]%mod);IDFT(f,len);
	IMP(n+m-1,write(f[i])),putchar(' ');
}

CompilationN/AN/ACompile ErrorScore: N/A


Judge Duck Online | 评测鸭在线
Server Time: 2024-10-05 11:37:03 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用