样例没过求调
查看原帖
样例没过求调
1010650
Expert_Dreamer楼主2024/10/5 14:48
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 2000001
const int mod=998244353;
int n,f[N],b[N],c[N],r[N],m,g[N],fr[N],gr[N],gr_inv[N],q[N],R[N],d[N];
int ksm(int a,int k){
    int res=1;
    while(k){
        if(k&1) res=res*a%mod;
        a=a*a%mod;
        k>>=1;
    }
    return res;
}
void ntt(int a[],int n,int x) {
	for(int i=0;i<n;i++) if(i<r[i]) swap(a[i],a[r[i]]);
	for(int i=1;i<n;i<<=1) {
		int z=ksm(3,(mod-1)/(i*2));
		for(int j=0;j<n;j+=(i*2)) {
			int t1,t2,g=1;
			for(int k=0;k<i;k++,g=g*z%mod) {
				t1=a[j+k],t2=g*a[j+k+i]%mod;
				a[j+k]=(t1+t2)%mod,a[j+k+i]=(t1-t2+mod)%mod;
			}
		}
	}
	if(x==1) return;
	int inv=ksm(n,mod-2); 
	reverse(a+1,a+n);
	for(int i=0;i<n;i++) a[i]=a[i]*inv%mod;
}
void work(int d,int *a,int *b) {
	if(d==1){
        b[0]=ksm(a[0],mod-2);
        return;
    }
	work((d+1)/2,a,b);
	int l=0,o=1;
	while(o<(d*2)) o*=2,l++;
	for(int i=1;i<o;i++) r[i]=(r[i/2]/2)|((i&1)<<(l-1));
	for(int i=0;i<d;i++) c[i]=a[i];
	for(int i=d;i<o;i++) c[i]=0;
	ntt(c,o,1),ntt(b,o,1);
	for(int i=0;i<o;i++) b[i]=(2-c[i]*b[i]%mod+mod)%mod*b[i]%mod;
	ntt(b,o,-1);
	for(int i=d;i<o;i++) b[i]=0;
}
void mul(int n,int m,int *a,int *b){
	int len=1,l=0;
	for(;len<=n+m;len<<=1,l++);
	for(int i=1;i<len;i++) r[i]=(r[i/2]/2)|((i&1)<<(l-1));
	ntt(a,len,1),ntt(b,len,1);
	for(int i=0;i<len;i++)a[i]=(a[i]*b[i])%mod;
	ntt(a,len,-1);
}
void ds(int n,int *a,int *b){
	for(int i=1;i<n;i++)b[i-1]=i*a[i]%mod;
	b[n-1]=0;
}
void dsinv(int n,int *a,int *b){
	for(int i=1;i<n;i++)b[i]=a[i-1]*ksm(i,mod-2)%mod;
	b[0]=0;
}
void Ln(int n,int *f,int *g){
	ds(n,f,fr),work(n,f,gr);
	int lim=1,m=0;
	while(lim<(n*2)) lim*=2,m++;
	for(int i=1;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(m-1));
	ntt(fr,lim,1),ntt(gr,lim,1);
	for(int i=0;i<lim;i++)fr[i]=fr[i]*gr[i]%mod;
	ntt(fr,lim,-1);
	dsinv(n,fr,g);
}
void Exp(int n,int *f,int *g){
	if(n==1){
		g[0]=1;
		return;
	}
	Exp(n+1>>1,f,g);
	int lim=1,m=0;
	while(lim<(n*2)) lim*=2,m++;
	for(int i=1;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(m-1));
	for(int i=0;i<2*n;i++) c[i]=d[i]=0;
	Ln(n,g,c);
	for(int i=0;i<n;i++)d[i]=f[i];
	ntt(g,n,1);
	ntt(c,n,1);
	ntt(d,n,1);
	for(int i=0;i<lim;i++)g[i]=(1-c[i]+d[i]+mod)%mod*g[i]%mod;
	ntt(g,lim,-1);
	for(int i=n;i<lim;i++)g[i]=0;
}
signed main(){
	cin>>n;
	for(int i=0;i<n;i++) cin>>f[i];
	Exp(n,f,q);
	for(int i=0;i<n;i++) cout<<q[i]<<" ";
}
2024/10/5 14:48
加载中...