写多项式的时候,发现把多项式乘法逆的代码贴进去后Debug会在主函数都没有进入(光标)就RE,chkstk_ms报错,or了一个0x0,如果把主函数中逆元那句话删去,就没有事情了,这件事情也只在DevC++上出现。
编译条件:-Wl,--stack=202400000,-std=c++14
代码:
#include<bits/stdc++.h>
using namespace std;
#define MOD 998244353
#define ll long long
#define G 3
#define GI 332748118
const int MAXN=600001;
int rev[MAXN];
ll qp(ll a,ll b){
ll ans=1;
while(b){if(b&1){ans=(ans*a)%MOD;}a=(a*a)%MOD;b>>=1;}
return ans;
}
struct poly{
ll poly1[MAXN];
int N;
void NTT(int n,int type){
for(int i=1;i<n;i++){if(i<rev[i])swap(poly1[i],poly1[rev[i]]);}
for(int len=2,m=1;len<=n;m=len,len<<=1){
ll W=qp(type==1?G:GI,(MOD-1)/len);
for(int l=0,r=len-1;r<=n;l+=len,r+=len){
ll w=1;
for(int p=l,lim=l+m;p<lim;p++,w=w*W%MOD){
ll x=poly1[p],y=poly1[p+m]*w%MOD;
poly1[p]=(x+y)%MOD,poly1[p+m]=(x-y+MOD)%MOD;
}
}
}
}
void clear(){
memset(poly1,0,sizeof(poly1));
}
void operator=(const poly &b){
N=b.N;
for(int i=0;i<=N;i++){
poly1[i]=b.poly1[i];
}
}
ll& operator[](const int i){
return poly1[i];
}
};
void multiply(poly &a,poly &b){
int len=a.N+b.N,k=1,l=0;
for(k=1;k<=len;k<<=1,++l);
for(int i=0;i<k;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
a.NTT(k,1);
b.NTT(k,1);
for(int i=0;i<k;i++){a.poly1[i]=a.poly1[i]*b.poly1[i]%MOD;}a.NTT(k,-1);
ll inv=qp(k,MOD-2);
for(int i=0;i<=len;++i){a.poly1[i]=inv*a.poly1[i]%MOD;}
}
static poly f0;
void inv(poly a,int n,poly&ans){
if(n==1){ans.poly1[0]=qp(a.poly1[0],MOD-2);ans.N=1;return;}
f0.clear();
inv(a,(n+1)>>1,f0);
int len=n*2,k=1,l=0;
for(k=1;k<=len;k<<=1,++l);
for(int i=0;i<k;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
for(int i=n;i<k;i++){a[i]=0;}
a.NTT(k,1);
f0.NTT(k,1);
for(int i=0;i<k;i++){ans.poly1[i]=f0[i]*((2-a[i]*f0[i]%MOD+MOD)%MOD)%MOD;}
ans.NTT(k,-1);
ll inv=qp(k,MOD-2);
for(int i=0;i<k;++i){ans.poly1[i]=inv*ans.poly1[i]%MOD;}
for(int i=n;i<=k;i++){ans[i]=0;}
}
poly a,b;
int main(){
int n;
cin>>n;
a.N=n;
for(int i=0;i<n;i++){int x;scanf("%d",&x);a.poly1[i]=(x+MOD)%MOD;}
inv(a,n,b);
for(int i=0;i<n;i++){int x;printf("%lld ",b.poly1[i]);}
}