记录编号	498465	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]疯狂的求和问题	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	2.432 s
提交时间	2018-06-14 20:14:37	内存使用	14.49 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1048600,p=998244353,g=3;
void pow_table(int);
void NTT(int*,int,int);
int qpow(int,int);
int prime[maxn/20],pw[maxn>>1];
char s[105];
int n,m,A[maxn],B[maxn],fac[maxn>>1],fac_inv[maxn>>1];
int main(){
	freopen("Crazy_Sum.in","r",stdin);
	freopen("Crazy_Sum.out","w",stdout);
	scanf("%s %d",s,&m);
	int len=strlen(s);
	for(int i=0;i<len;i++)n=(n*10ll+s[i]-'0')%p;
	n%=p;
	m++;
	fac[0]=fac_inv[0]=1;
	for(int i=1;i<=m;i++)fac[i]=(long long)fac[i-1]*i%p;
	fac_inv[m]=qpow(fac[m],p-2);
	for(int i=m-1;i;i--)fac_inv[i]=(long long)fac_inv[i+1]*(i+1)%p;
	pow_table(m);
	for(int i=1;i<=m;i++)if((A[i]=A[i-1]+pw[i])>=p)A[i]-=p;
	for(int i=0;i<=m;i++){
		A[i]=(long long)A[i]*fac_inv[i]%p;
		B[i]=fac_inv[i];
		if(i&1)B[i]=p-B[i];
	}
	int N=1;
	while(N<=(m<<1))N<<=1;
	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);
	int ans=0;
	for(int i=0,C=1;i<=m&&C;i++,C=(long long)C*(n-i+1)%p)
		ans=(ans+(long long)A[i]*C)%p;
	if(ans<0)ans+=p;
	printf("%d",ans);
	return 0;
}
void pow_table(int n){
	pw[1]=1;
	for(int i=2;i<=n;i++){
		if(!pw[i]){
			prime[++prime[0]]=i;
			pw[i]=qpow(i,n-1);
		}
		for(int j=1;j<=prime[0]&&i*prime[j]<=n;j++){
			pw[i*prime[j]]=(long long)pw[i]*pw[prime[j]]%p;
			if(i%prime[j]==0)break;
		}
	}
}
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-(p-1)/k);
		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;
				if((A[i+j]=a+b)>=p)A[i+j]-=p;
				if((A[i+j+(k>>1)]=a-b)<0)A[i+j+(k>>1)]+=p;
			}
		}
	}
	if(tp<0){
		int inv=qpow(n,p-2);
		for(int i=0;i<n;i++)A[i]=(long long)A[i]*inv%p;
	}
}
int qpow(int a,int b){
	int ans=1;
	for(;b;b>>=1,a=(long long)a*a%p)if(b&1)ans=(long long)ans*a%p;
	return ans;
}
/*
Newton's Formula:
f(x) = \sum_{i=0}^n a_i x^i
then f(n) = \sum_{i=0}^n {n \choose i} r_i
*/