菜鸡求助ntt
查看原帖
菜鸡求助ntt
35754
whiteqwq楼主2021/1/1 14:29

突然想给自己的多项式代码封装一下(再压一压行)

结果编译完直接停止工作了。。。

求助一下是有什么奇怪的锅

#include<stdio.h>
const int maxn=5000005,mod=998244353,G=3;
int n,m;
int p[maxn];
struct poly{
	int len;
	int a[maxn];
	poly(){
		len=a[0]=0;
	}
	void print(){
		for(int i=0;i<=len;i++)
			printf("%d%c",a[i],i==len? '\n':' ');
	}
}a,b,c;
inline void swp(int &a,int &b){
	a+=b,b=a-b,a-=b;
}
int ksm(int a,int b,int res=1){
	for(;b;a=1ll*a*a%mod,b>>=1)
		res=(b&1)? 1ll*res*a%mod:res;
	return res;
}
int getlen(int x){
	int res=0;
	for(int mul=1;mul<=x;mul<<=1,res++);
	return res;
}
poly NTT(poly x,int opt){
	int r=getlen(x.len),lim=1<<r,invlim=ksm(lim,mod-2),invG=ksm(G,mod-2);
	poly res=x;
	res.len=lim;
	for(int i=0;i<lim;i++)
		p[i]=(p[i>>1]>>1)|((i&1)<<(r-1));
	for(int i=0;i<lim;i++)
		if(i<p[i])
			swp(res.a[i],res.a[p[i]]);
	for(int now=1;now<lim;now<<=1){
		int omega=ksm(opt==1? G:invG,(mod-1)/now/2);
		for(int pos=0;pos<lim;pos+=(now<<1))
			for(int i=0,mul=1;i<now;i++,mul=1ll*mul*omega%mod){
				int x=res.a[pos+i],y=1ll*res.a[pos+i+now]*mul%mod;
				res.a[pos+i]=(x+y)%mod,res.a[pos+i+now]=(x-y+mod)%mod;
			}
	}
	if(opt==-1)
		for(int i=0;i<=res.len;i++)
			res.a[i]=1ll*res.a[i]*invlim%mod;
	return res;
}
poly mul(poly a,poly b){
	poly tmpa=NTT(a,1),tmpb=NTT(b,1),res;
	res.len=tmpa.len+tmpb.len;
	for(int i=0;i<=tmpa.len+tmpb.len;i++)
		res.a[i]=1ll*tmpa.a[i]*tmpb.a[i]%mod;
	return NTT(res,-1);
}
int main(){
	scanf("%d%d",&n,&m);
	a.len=n,b.len=m;
	for(int i=0;i<=n;i++)
		scanf("%d",&a.a[i]),a.a[i]%=mod;
	for(int i=0;i<=m;i++)
		scanf("%d",&b.a[i]),b.a[i]%=mod;
	c=mul(a,b),c.print();
	return 0;
}
2021/1/1 14:29
加载中...