代码

#include <cstdio>
#include <ctime>
#include <vector>
#include <cstring>
#include <algorithm>
#define ull unsigned long long
#define int unsigned long long
#define N 4000005
using std::vector;
typedef vector<int> poly;
const int MOD=998244353;
namespace iobuff{
	const int LEN=1000000;
	char in[LEN+5], out[LEN+5];
	char *pin=in, *pout=out, *ed=in, *eout=out+LEN;
	inline char gc(void)
	{
		return pin==ed&&(ed=(pin=in)+fread(in, 1, LEN, stdin), ed==in)?EOF:*pin++;
	}
	inline void pc(char c)
	{
		pout==eout&&(fwrite(out, 1, LEN, stdout), pout=out);
		(*pout++)=c;
	}
	inline void flush()
	{ fwrite(out, 1, pout-out, stdout), pout=out; }
	template<typename T> inline void scan(T &x)
	{
		static int f;
		static char c;
		c=gc(), f=1, x=0;
		while(c<'0'||c>'9') f=(c=='-'?-1:1), c=gc();
		while(c>='0'&&c<='9') x=10*x+c-'0', c=gc();
		x*=f;
	}
	template<typename T> inline void putint(T x, char div)
	{
		static char s[20];
		static int top;
		top=0;
		x<0?pc('-'), x=-x:0;
		while(x) s[top++]=x%10, x/=10;
		!top?pc('0'), 0:0;
		while(top--) pc(s[top]+'0');
		pc(div);
	}
}
using namespace iobuff;
int tt, tt1;
int iv[N], iiv[N], fac[N], tp;
inline void init(void) { tp=2; iv[0]=iv[1]=iiv[0]=iiv[1]=1, fac[0]=fac[1]=1; }
inline void ext(int x)
{
	for(; tp<=x; ++tp)
	{
		iv[tp]=MOD-1ll*(MOD/tp)*iv[MOD%tp]%MOD;
	}
}
char c1;
inline int mval(int x) { return x>=MOD?x-MOD:x; }
inline void inc(int &x, int a) { x=mval(x+a); }
inline void dec(int &x, int a) { x=mval(MOD+x-a); }
inline int qpow(int x, int p)
{ int ret=1; while(p) { if(p&1) ret=1ll*ret*x%MOD; p>>=1, x=1ll*x*x%MOD; } return ret; }
inline int inv(int x) { return qpow(x, MOD-2); }
namespace Poly{
	namespace Poly_Basic{
		inline void print(const poly &a) { for(int x:a) printf("%llu ", x); puts(""); }
		inline void printbuff(const poly &a) { for(int x:a) putint(x, ' '); pc('\n'); }
		inline poly to_poly(int *a, int n) { poly ret; ret.resize(n); memcpy((int*)&ret[0], a, sizeof(int)*n); return ret; }
		inline poly deri(poly a)
		{
			for(int i=0; i<a.size()-1; ++i) a[i]=1ll*a[i+1]*(i+1)%MOD;
			a.pop_back();
			return a;
		}
	}
	using namespace Poly_Basic;
	namespace NTT{
		const int g=3;
		int rev[N], wn[N], up=1;
		inline int glim(int n)
		{
			int l=0;
			while(n) n>>=1, ++l;
			return l;
		}
		inline void init(int l)
		{
			tt1-=clock();
			for(int i=1; i<(1<<l); ++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
			for(int i=up; i<(1<<l); i<<=1)
			{
				wn[i]=1;
				int mw=qpow(g, (MOD-1)/(i<<1));
				for(int j=1; j<i; ++j) wn[i+j]=1ll*wn[i+j-1]*mw%MOD;
			}
			if((1<<l)>up) up=(1<<l);
			tt1+=clock();
		}
		void ntt(int *f, int n, int mod)
		{
			tt1-=clock();
			tt+=n*__builtin_ctz(n);
			for(int i=0; i<n; ++i) if(i<rev[i]) std::swap(f[i], f[rev[i]]);
			for(int len=2; len<=n; len<<=1)
			{
				int c=len>>1;
				for(int i=0; i<n; i+=len) for(int j=i, *w=wn+c; j<i+c; ++j, ++w)
				{
					int x=f[j], y=f[j+c]**w%MOD;
					f[j]=x+y, f[j+c]=MOD+x-y;
//					f[j]=mval(x+y), f[j+c]=mval(MOD+x-y);
//					f[j]=mval(x+y), f[j+c]=mval(MOD+x-y);
				}
			}
			for(int i=0; i<n; ++i) f[i]%=MOD;
			if(mod)
			{
				std::reverse(f+1, f+n);
				int iv=inv(n);
				for(int i=0; i<n; ++i) f[i]=f[i]*iv%MOD;
			}
			tt1+=clock();
		}
	}
	using NTT::init;
	using NTT::ntt;
	using NTT::glim;
	namespace EXP{
		const int Blim=4, B=1<<Blim, Thre=128;
		int f[N], G[N], rn;
		poly H[10][B];
		void exp_init(const poly &g, int lim)
		{
			ext(1<<lim);
			std::fill(f, f+(1<<lim), 0);
			std::fill(G, G+(1<<lim), 0);
			memcpy(G, g.data(), sizeof(int)*std::min((int)g.size(), (1ull<<lim)));
			for(int i=0; i<=(1<<lim); ++i) G[i]=1ll*G[i]*i%MOD;
			for(int i=lim; i>=Blim; i-=Blim)
			{
				if((1<<i)<=Thre) break;
				int len=1<<(i-Blim);
				init(i-Blim+1);
				int id=i/Blim;
				for(int j=0; j<B-1; ++j)
				{
					if(j*len>=rn) break;
					H[id][j].resize(len*2);
					memcpy(H[id][j].data(), G+j*len, sizeof(int)*(2*len));
					ntt(H[id][j].data(), 2*len, 0);
				}
			}
		}
		void exp(int lim, int l, int r)
		{
			if(l>=rn) return;
			if(r-l<=Thre)
			{
				for(int i=l; i<r; ++i)
				{
					if(i==0) f[i]=1;
					else f[i]=1ll*iv[i]*f[i]%MOD;
					for(int j=i+1; j<r; ++j) f[j]=(f[j]+1ll*f[i]*G[j-i])%MOD;
				}
				return;
			}
			int len=1<<(lim-Blim), id=lim/Blim, L=(std::min(r, rn)-l+len-1)/len;
			poly cur[B];
			for(int i=0; i<L; ++i) cur[i].resize(len*2);
			for(int i=0; i<L; ++i)
			{
				if(i!=0)
				{
					init(lim-Blim+1);
					ntt(cur[i].data(), 2*len, 1);
					for(int j=0; j<len; ++j) inc(f[j+len*i+l], cur[i][j+len]);
				}
				exp(lim-Blim, l+i*len, l+i*len+len);
				if(i!=L-1)
				{
					memcpy(cur[i].data(), f+l+i*len, sizeof(int)*len);
					std::fill(cur[i].data()+len, cur[i].data()+2*len, 0);
					init(lim-Blim+1);
					ntt(cur[i].data(), 2*len, 0);
					for(int j=i+1; j<L; ++j)
					{
						for(int k=0; k<2*len; ++k)
							cur[j][k]=(cur[j][k]+1ll*cur[i][k]*H[id][j-i-1][k])%MOD;
					}
				}
			}
		}
		inline void exp(const poly &F, poly &g, int n)
		{
			int lim=glim(n-1);
			rn=n;
//			fprintf(stderr, "fa %d\n", 1<<lim);
			exp_init(F, lim);
	fprintf(stderr, "%llu %llu\n", tt, tt1);
			exp(lim, 0, 1<<lim);
			g.resize(n);
			memcpy(g.data(), f, sizeof(int)*n);
		}
		inline poly exp(const poly &a, int n)
		{
			poly ret;
			exp(a, ret, n);
			return ret;
		}
	}
	using EXP::exp;
}
using namespace Poly;
char c2;
int n;
poly f;
#include <random>
std::mt19937 rnd(time(0));
signed main()
{
//	freopen("in.in", "r", stdin);
//	freopen("out.out", "w", stdout);
	n=100000;
	init();
	scan(n);
	f.resize(n);
	for(int i=0; i<n; ++i) f[i]=rnd()%MOD;//scan(f[i]);
	printbuff(exp(f, n));
	flush();
	fprintf(stderr, "%llu %llu sz %d\n", tt, tt1, (&c2-&c1)/1024/1024);
	return 0;
}

评测结果