记录编号	395414	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 求和	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	1.408 s
提交时间	2017-04-15 21:37:16	内存使用	4.29 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=262200,p=998244353,g=3;
void NTT(int*,int,int);
void getinv(int*,int*,int);
int qpow(int,int,int);
int n,N=1,A[maxn],fac[maxn],fac_inv[maxn],ans=0;
int main(){
	freopen("heoi2016_sum.in","r",stdin);
	freopen("heoi2016_sum.out","w",stdout);
	scanf("%d",&n);
	while(N<=n)N<<=1;
	fac[0]=fac_inv[0]=1;
	for(int i=1;i<=n;i++)fac[i]=(long long)fac[i-1]*i%p;
	fac_inv[n]=(long long)qpow(fac[n],p-2,p)*(p-2)%p;
	for(int i=n-1;i;i--)fac_inv[i]=(long long)fac_inv[i+1]*(i+1)%p;
	getinv(fac_inv,A,N);
	for(int i=0;i<=n;i++)ans=(ans+(long long)A[i]*fac[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;
	}
}
void getinv(int *A,int *C,int n){
	static int B[maxn];
	fill(C,C+(n<<1),0);
	C[0]=qpow(A[0],p-2,p);
	for(int k=2;k<=n;k<<=1){
		copy(A,A+k,B);
		fill(B+k,B+(k<<1),0);
		NTT(B,k<<1,1);
		NTT(C,k<<1,1);
		for(int i=0;i<(k<<1);i++)C[i]=C[i]*((2-(long long)B[i]*C[i]%p+p)%p)%p;
		NTT(C,k<<1,-1);
		fill(C+k,C+(k<<1),0);
	}
}
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;
}