求助
查看原帖
求助
537046
大眼仔Happy楼主2024/5/28 18:15

rt,封装写的,会有什么危险的地方吗:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=(1<<21)+5;
const ll mod=998244353,g=3,ig=332748118;
int inline read(){
	int num=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){num=(num<<3)+(num<<1)+(ch^48);ch=getchar();}
	return num*f;
}
int n,m;
int pos[N];
ll qp(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll inc(ll a,ll b){return a+b>=mod?a+b-mod:a+b;}
ll dec(ll a,ll b){return a<b?a-b+mod:a-b;}
void rev(int L){for(int i=0;i<L;i++)pos[i]=(pos[i>>1]>>1)|(i&1?L>>1:0);}
struct poly{
	vector<ll>c;
	int L,n;
	ll &operator [](ll x){return c[x];}
	void init(int x){L=1;while(L<=x)L<<=1;c.resize(L+1);}
	void get(int x){
		init(x);n=x;
		for(int i=0;i<=n;i++)c[i]=read();
	}
	void NTT(int opt){
		for(int i=0;i<L;i++)
			if(i<pos[i])swap(c[i],c[pos[i]]);
		for(int len=1;len<L;len<<=1){
			ll o=qp((opt==1?g:ig),(mod-1)/(len<<1));
			for(int i=0;i<L;i+=len<<1){
				ll s=1;
				for(int j=i;j<i+len;j++){
					ll t=s*c[len+j]%mod;
					c[len+j]=dec(c[j],t);
					c[j]=inc(c[j],t);
					s=s*o%mod;
				}
			}
		}
		if(opt==-1){
			ll iL=qp(L,mod-2);
			for(int i=0;i<L;i++)c[i]=c[i]*iL%mod;
		}
	}
	poly friend operator + (poly A,poly B){
		for(int i=0;i<B.n;i++)	
			A[i]=inc(A[i],B[i]);
		return A;
	}
	poly friend operator - (poly A,poly B){
		for(int i=0;i<B.n;i++)
			A[i]=dec(A[i],B[i]);
		return A;
	}
	poly operator * (ll num){
		for(int i=0;i<n;i++)
			c[i]=c[i]*num%mod;
		return *this;
	}
	poly friend operator * (poly A,poly B){
		A.init(A.n+B.n);
		B.init(A.n+B.n);
		rev(A.L);A.NTT(1);B.NTT(1);
		for(int i=0;i<A.L;i++)A[i]=A[i]*B[i]%mod;
		A.NTT(-1);A.n+=B.n;
		return A;
	}
}F,G;
poly inv(poly F,int n){
	poly G;
	if(n==1){
		G.init(0);
		G[0]=qp(F[0],mod-2);
		return G;
	}
	G=inv(F,n+1>>1);
	F.init(n<<1);
	G.init(n<<1);
	for(int i=n;i<F.L;i++)F[i]=0,G[i]=0;
	rev(G.L);F.NTT(1);G.NTT(1);
	for(int i=0;i<G.L;i++)G[i]=(2ll-F[i]*G[i]%mod+mod)*G[i]%mod;
	G.NTT(-1);
	for(int i=n;i<G.L;i++)G[i]=0;
	return G;
}
int main(){
	n=read();
	F.get(n-1);G=inv(F,n);
	for(int i=0;i<n;i++)printf("%lld ",G[i]);
	return 0;
}

record

2024/5/28 18:15
加载中...