关于DEV
  • 板块学术版
  • 楼主ReqCxmChtChr
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/12/27 09:08
  • 上次更新2023/10/24 06:28:13
查看原帖
关于DEV
421451
ReqCxmChtChr楼主2022/12/27 09:08

写多项式的时候,发现把多项式乘法逆的代码贴进去后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]);}
}
2022/12/27 09:08
加载中...