请神仙来优化常数,蒟蒻优化不动了
查看原帖
请神仙来优化常数,蒟蒻优化不动了
29093
Deep_KevinLILDOGDOG楼主2020/9/24 17:42
#include<bits/stdc++.h>
#define vi vector<int>
using namespace std;

int mod=998244353;
int ksm(int x,int t){
	int tot=1;
	while(t){
		if(t&1) tot=1ll*tot*x%mod;
		x=1ll*x*x%mod;
		t/=2;
	}
	return tot;
}
const int N=600010;//2<<18
int poor[2400010];
int fac[N],finv[N],n,limit,where[N];
int*w[2][19],*now=poor;

inline char nc()
{
    static const int BS = 1 << 22;
    static unsigned char buf[BS],*st,*ed;
    if(st == ed) ed = buf + fread(st=buf,1,BS,stdin);
    return st == ed ? EOF : *st++;
}
#define nc getchar
inline int read()
{
    char ch;
    int res = 0; bool flag = 0;
    while (!isdigit(ch = nc()));
    while (ch >= '0' and ch <= '9')
    {
        res = (res << 1) + (res << 3) + (ch - '0');
        ch = nc();
    }
    return res;
}

void pre(){
	fac[0]=1;for(int i=1;i<=600000;i++) fac[i]=1ll*fac[i-1]*i%mod;
	finv[600000]=ksm(fac[600000],mod-2);
	for(int i=599999;i>=0;i--) finv[i]=1ll*finv[i+1]*(i+1)%mod;
	for(int u=0,l=2;u<19;u++,l<<=1){
		w[1][u]=now;now+=l+1;
		w[0][u]=now;now+=l+1;
		w[1][u][0]=1;w[1][u][1]=ksm(3,(mod-1)/l);
		for(int i=2;i<=l;i++) w[1][u][i]=1ll*w[1][u][i-1]*w[1][u][1]%mod;
		for(int i=0;i<=l;i++) w[0][u][i]=w[1][u][l-i];
	}
}

void prepare(int n){
	int l=0;limit=1;
	while(limit<=n) limit<<=1,l++;
	for(int i=0;i<limit;i++) where[i]=((where[i>>1]>>1) | ((i&1)<<(l-1)));
}

void DFT(vi&now,int op){
	for(int i=0;i<limit;i++) if(i<where[i]) swap(now[i],now[where[i]]);
	for(int u=0,l=1,r=2;r<=limit;l=r,r<<=1,u++){
		for(int i=0;i<limit;i+=r){
			for(int v=0;v<l;v++){
				int x=i+v,y=i+l+v,a=now[x],b=1ll*now[y]*w[op][u][v]%mod;
				now[x]=(a+b>=mod?a+b-mod:a+b);
				now[y]=(a<b?a+mod-b:a-b);
			}
		}
	}
	if(!op){
		int tmp=ksm(limit,mod-2);
		for(int i=0;i<limit;i++) now[i]=1ll*now[i]*tmp%mod;
	}
}

vi operator*(vi f,vi g){
	int tot=f.size()+g.size()-2;
	prepare(tot);f.resize(limit);g.resize(limit);
	DFT(f,1);DFT(g,1);
	for(int i=0;i<limit;i++) f[i]=1ll*f[i]*g[i]%mod;
	DFT(f,0);f.resize(tot+1);
	return f;
}

void INV(vi&f){
	int n=f.size();
	if(n==1) {f[0]=ksm(f[0],mod-2);return ;}
	vi f0=f;f0.resize((n+1)/2);INV(f0);
	prepare(n+(n+1)/2*2-3);
	f.resize(limit);f0.resize(limit);
	DFT(f,1);DFT(f0,1);
	for(int i=0;i<limit;i++) f[i]=1ll*f0[i]*(mod+2-1ll*f[i]*f0[i]%mod)%mod;
	DFT(f,0);f.resize(n);
}

int main(){
	//freopen("P3711_2.in","r",stdin);
	//freopen("ans.out","w",stdout);
	n=read();
	vi A;A.resize(n+1);pre();
	for(int i=0;i<=n;i++) A[i]=read(),A[i]=1ll*A[i]*fac[i]%mod;
	vi f,g;f.resize(n+1);g.resize(n+1);
	for(int i=0;i<=n;i++) f[i]=finv[i],g[i]=finv[i+1];
	INV(g);f=f*g;f.resize(n+1);
	for(int i=0;i<=n/2;i++) swap(f[i],f[n-i]);
	f=f*A;printf("%d ",A[0]);
	for(int i=1;i<=n+1;i++) printf("%lld ",1ll*f[n+i-1]*finv[i]%mod);
}
2020/9/24 17:42
加载中...