突然想给自己的多项式代码封装一下(再压一压行)
结果编译完直接停止工作了。。。
求助一下是有什么奇怪的锅
#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;
}