记录编号	424916	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[郑州集训 2017]NOI模拟题7.1	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.080 s
提交时间	2017-07-14 14:00:55	内存使用	0.33 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=3010,p=119<<23|1;
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int dec(int x,int y){x-=y;return x<0?x+p:x;}
int mul(int x,int y){return (ll)x*y%p;}
int power(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=mul(x,x))
		if (y&1) ans=mul(ans,x);
	return ans;
}
int w[N],iw[N];
void init(int n){
	w[0]=1;w[1]=power(3,(p-1)/n);
	for (int i=2;i<=n;i++) w[i]=mul(w[i-1],w[1]);
	for (int i=0;i<=n;i++) iw[i]=w[n-i];
}
void fft(int n,int *a,int *w){
	for (int i=0,j=0;i<n;i++){
		if (i<j) swap(a[i],a[j]);
		for (int k=n>>1;(j^=k)<k;k>>=1);
	}
	for (int i=2;i<=n;i<<=1){
		int m=i>>1,step=n/i;
		for (int j=0;j<n;j+=i)
		for (int k=0,pos=0;k<m;k++,pos+=step){
			int t=mul(a[j+k+m],w[pos]);
			a[j+k+m]=dec(a[j+k],t);
			a[j+k]=inc(a[j+k],t);
		}
	}
	if (w==iw){
		int del=power(n,p-2);
		for (int i=0;i<n;i++) a[i]=mul(a[i],del);
	}
}
const int size=1<<11;
void getmod(int *a){
	for (int i=0;i<size;i++)
		a[i+1]+=a[i]/10,a[i]%=10;
}
int n,x[N],ans[N];
void getpower(int *x,int y,int *ans){
	ans[0]=1;
	for (;y;y>>=1){
		fft(size,x,w);
		if (y&1){
			fft(size,ans,w);
			for (int i=0;i<size;i++) ans[i]=mul(ans[i],x[i]);
			fft(size,ans,iw);
			getmod(ans);
		}
		for (int i=0;i<size;i++) x[i]=mul(x[i],x[i]);
		fft(size,x,iw);
		getmod(x);
	}
}
int main()
{
	freopen("zweitel.in","r",stdin);
	freopen("zweitel.out","w",stdout);
	scanf("%d",&n);
	init(size);
	x[1]=5;
	getpower(x,n,ans);
	int p=size-1;
	while (!ans[p]) p--;
	for (;p>=0;p--) printf("%d",ans[p]);
	puts("");
	return 0;
}