有没有dalao帮忙卡一卡常
查看原帖
有没有dalao帮忙卡一卡常
1125685
Frielen楼主2024/11/20 13:19

rt

#include<cstdio>
#include<cmath>
#include<algorithm>
using std::swap;
#define ldb long double
#define int long long
const int N=4e5+9,limit=32000;
const ldb pi=acos(-1.0);
struct comp{
    ldb x,y;
    inline comp (ldb xx=0,ldb yy=0){x=xx,y=yy;}
}a1[N],a2[N],b[N];
constexpr int p=998244353;
int r[N];
static comp operator + (comp a,comp b){return comp{a.x+b.x,a.y+b.y};}
static comp operator - (comp a,comp b){return comp{a.x-b.x,a.y-b.y};}
static comp operator * (comp a,comp b){return comp{a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
int n,m,kk;
static void FFT(int lim,comp *s,int typ){
	for(int i=0;i<lim;i++) if(i<r[i]) swap(s[i],s[r[i]]);
	comp w,x,y,Wnk;
	for(int mid=1;mid<lim;mid<<=1){
		Wnk={cosl(pi/mid),typ*sinl(pi/mid)};
		for(int ri=mid<<1,j=0;j<lim;j+=ri){
            w={1,0};
            for(int k=0;k<mid;k++,w=w*Wnk){
                x=s[j+k],y=w*s[j+mid+k];
                s[j+k]=x+y;
                s[j+mid+k]=x-y;
            }
        }
	}
}
static void NTT(int *x,int *y,int len,int *ans){
	int lim=1,l=0;
	comp X1[N],X2[N],Y[N];
	for(int i=0;i<len;i++){
		X1[i]={(x[i]/limit),(x[i]%limit)};
		X2[i]={(x[i]/limit),(-x[i]%limit)};
		Y[i]={(y[i]/limit),(y[i]%limit)};
	}
	while(lim<=len) lim<<=1,l++;
	for(int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	FFT(lim,X1,1);
	FFT(lim,X2,1);
	FFT(lim,Y,1);
	for(int i=0;i<lim;i++) Y[i].x/=lim,Y[i].y/=lim;
  	for(int i=0;i<lim;i++) X1[i]=X1[i]*Y[i];
  	for(int i=0;i<lim;i++) X2[i]=X2[i]*Y[i];
  	FFT(lim,X1,-1);
  	FFT(lim,X2,-1);
  	for(int i=0;i<len;i++){
    	int A1,A2,A3,A4;
    	A1=(int)floor((X1[i].x+X2[i].x)/2+0.49)%p;
    	A2=(int)floor((X1[i].y+X2[i].y)/2+0.49)%p;
    	A3=((int)floor(X1[i].y+0.49)-A2)%p;
    	A4=((int)floor(X2[i].x+0.49)-A1)%p;
    	ans[i]=((A1*limit+(A2+A3))%p*limit%p+A4)%p;
    	ans[i]=(ans[i]+p)%p;
  	}
}
inline int qpow(int a,int q){
	int res=1;
	while(q){
		if(q&1) res=(res*a)%p;
		a=(a*a)%p;
		q>>=1;
	}
	return (res%p);
}
int A1[N],c[N],d[N],ans[N];
void deri/*derivation*/(int *A,int *B,int len){
	for(int i=1;i<len;i++) B[i-1]=A[i]*i%p;
	B[len-1]=0;
}
void inte/*integral*/(int *A,int *B,int len){
	for(int i=1;i<len;i++) B[i]=A[i-1]*qpow(i,p-2)%p;
	B[0]=0;
}
int ans1[N],ans2[N],ans3[N],C[N];
inline void NTT_inverse(int len,int *a,int *Bb){
	if(len==1){Bb[0]=qpow(a[0],p-2);return;}
	NTT_inverse(len>>1,a,Bb);
	NTT(a,Bb,len,c);
	NTT(c,Bb,len,d);
	for(int i=0;i<len;i++) Bb[i]=(Bb[i]+Bb[i])%p;
	for(int i=0;i<len;i++) Bb[i]=(Bb[i]+p-d[i])%p;
}
inline void Getln(int *A,int *B,int len){
	deri(A,ans1,len);
	NTT_inverse(len,A,ans2);
	NTT(ans1,ans2,len,C);
	inte(C,B,len);
}
int ln[N];
int Ans1[N],Ans2[N],Ans3[N];
inline void Getexp(int *A,int *B,int len){
	if(len==1){
		B[0]=1;
		return;
	}
	Getexp(A,B,len>>1);
	Getln(B,ln,len);
	int lim=1;
	while(lim<=len*2) lim<<=1;
    for(int i=0;i<len;i++) Ans1[i]=A[i];
    for(int i=len;i<lim;i++) ln[i]=Ans1[i]=0;
    for(int i=0;i<lim;i++) Ans1[i]=((Ans1[i]-ln[i])%p+p)%p;
    Ans1[0]++;
    NTT(Ans1,B,len,B);
    for(int i=len;i<lim;i++) B[i]=0;
}
signed main(){
	scanf("%lld",&n);
	for(int i=0;i<n;i++) scanf("%lld",&A1[i]);
    int now=1;
	while(now<n) now<<=1;
	Getexp(A1,Ans2,now);
	for(int i=0;i<n;i++) printf("%lld ",Ans2[i]);
	return 0;
}
2024/11/20 13:19
加载中...