记录编号	373858	评测结果	AAAAAAAAAA
题目名称	2272.[HEOI 2016] 求和	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	1.368 s
提交时间	2017-02-21 21:11:49	内存使用	3.29 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=262200,p=998244353,g=3;
void NTT(int*,int,int);
int qpow(int,int,int);
int n,N=1,f[maxn],A[maxn],B[maxn],ans=0;
int main(){
	freopen("heoi2016_sum.in","r",stdin);
	freopen("heoi2016_sum.out","w",stdout);
	scanf("%d",&n);
	while(N<=(n<<1))N<<=1;
	f[0]=1;
	for(int i=0;i<=n;i++){
		if(i)f[i]=(long long)f[i-1]*i%p;
		B[i]=qpow(f[i],p-2,p);
		if(i!=1)A[i]=(qpow(i,n+1,p)-1+p)%p*(long long)qpow((i-1+p)%p*(long long)f[i]%p,p-2,p)%p;
		else A[i]=(long long)(n+1)*B[i]%p;
		if(i&1)B[i]=(p-B[i])%p;
	}
	NTT(A,N,1);
	NTT(B,N,1);
	for(int i=0;i<N;i++)A[i]=(long long)A[i]*B[i]%p;
	NTT(A,N,-1);
	for(int i=0,pw=1;i<=n;i++,pw=(long long)pw*2%p)ans=(ans+(long long)pw*f[i]%p*A[i]%p)%p;
	printf("%d",ans);
	return 0;
}
void NTT(int *A,int n,int tp){
	for(int i=1,j=0,k;i<n-1;i++){
		k=n;
		do j^=(k>>=1);while(j<k);
		if(i<j)swap(A[i],A[j]);
	}
	for(int k=2;k<=n;k<<=1){
		int wn=qpow(g,(tp>0?(p-1)/k:(p-1)/k*(long long)(p-2)%(p-1)),p);
		for(int i=0;i<n;i+=k){
			int w=1;
			for(int j=0;j<(k>>1);j++,w=(long long)w*wn%p){
				int a=A[i+j],b=(long long)w*A[i+j+(k>>1)]%p;
				A[i+j]=(a+b)%p;
				A[i+j+(k>>1)]=(a-b+p)%p;
			}
		}
	}
	if(tp<0){
		int inv=qpow(n,p-2,p);
		for(int i=0;i<n;i++)A[i]=(long long)A[i]*inv%p;
	}
}
int qpow(int a,int b,int p){
	int ans=1;
	for(;b;b>>=1,a=(long long)a*a%p)if(b&1)ans=(long long)ans*a%p;
	return ans;
}