记录编号	363786	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 求和	最终得分	100
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	通过
代码语言	C++	运行时间	1.298 s
提交时间	2017-01-13 10:50:55	内存使用	8.03 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
typedef unsigned int UINT;
const int MAXN=1E6+10;
const UINT mod=998244353;
const UINT god=3;
inline UINT pow(UINT a,UINT b) {
	UINT ans=1;
	for(ans=1;b;b>>=1,a=1ull*a*a%mod) {
		if(b&1)ans=1ull*ans*a%mod;
	}return ans;
}
void rotate(UINT*a,int N) {
	for(int i=1,j=0;i<N;++i) {
		int k=N;
		do{k>>=1;j^=k;}while(j<k);
		if(i<j)std::swap(a[i],a[j]);
	}
}
void NTT(UINT*a,int N,const int&is) {
	rotate(a,N);
	for(int m=2;m<=N;m<<=1) {
		const int mh=m>>1;
		const UINT wn=pow(god,is==1?(mod-1)-(mod-1)/m:(mod-1)/m);
		for(int r=0;r<N;r+=m) {
			UINT w=1;
			UINT*b=a+r;
			UINT*c=a+r+mh;
			for(int k=0;k<mh;++k) {
				const UINT u=b[k];
				const UINT v=1ull*c[k]*w%mod;
				b[k]=(0ll+u+v)%mod;
				c[k]=(0ll+mod+u-v)%mod;
				w=1ull*w*wn%mod;
			}
		}
	}
	if(is<0) {
		const UINT inv=pow(N,mod-2);
		for(int i=0;i<N;++i) {
			a[i]=1ull*a[i]*inv%mod;
		}
	}
}
UINT nn[MAXN];
UINT invn[MAXN];
UINT JS[MAXN];
UINT invJS[MAXN];
int Cpre(int N) {
	JS[0]=1;++N;
	for(int i=1;i<=N;++i) {
		JS[i]=1ull*JS[i-1]*i%mod;
	}invJS[N]=pow(JS[N],mod-2);
	for(int i=N-1;i>=0;--i){
		invJS[i]=1ull*invJS[i+1]*(i+1)%mod;
		invn[i+1]=1ull*invJS[i+1]*JS[i]%mod;
	}--N;invn[0]=0;
	for(int i=0;i<=N+1;++i) {
		nn[i]=pow(i,N+1);
	}return 0;
}
inline UINT Psum(UINT k,UINT N) {
	return k==0?1:(k==1? N+1 : 1ull*(mod+nn[k]-1)%mod*(invn[k-1])%mod )*invJS[k]%mod;
}
inline UINT Usum(UINT k) {
	return k&1?1ull*(mod-1)*invJS[k]%mod:invJS[k];
}
inline UINT Mul2(UINT j) {
	return 1ull*pow(2,j)*JS[j]%mod;
}
UINT a[MAXN],b[MAXN],c[MAXN];


int main() {
	freopen("heoi2016_sum.in","r",stdin);
	freopen("heoi2016_sum.out","w",stdout);
	UINT N,len;
	//printf("%u",mod);
	scanf("%u",&N);
	Cpre(N);
	//Test(N);
	for(int i=0;i<=N;++i) {
		a[i]=Usum(i);
		b[i]=Psum(i,N);
		//printf("[%d] %9u\n",i,a[i]);
	}
	for(len=1;len<=N+1;len<<=1);len<<=1;
	NTT(a,len,1);
	NTT(b,len,1);
	for(int i=0;i<len;++i) {
		c[i]=1ull*a[i]*b[i]%mod;
	}NTT(c,len,-1);
	UINT ans=0;
	for(int i=0;i<=N;++i) {
		//printf("[%d]%16u %16u\n",i,c[i],Mul2(i));
		ans=(ans+1ull*Mul2(i)*c[i]%mod)%mod;
	}printf("%u\n",ans);
	fclose(stdin);fclose(stdout);
	return 0;
}