记录编号	593806	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]疯狂的机器人	最终得分	100
用户昵称	qyd	是否通过	通过
代码语言	C++	运行时间	0.483 s
提交时间	2024-09-14 13:48:52	内存使用	11.80 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e6+10;
const int mod=998244353;
const int root=3;
ll quick_pow(ll a,ll b)
{
	ll ret=1;
	for(;b;b>>=1,a=a*a%mod)
	  if(b&1)
	    ret=ret*a%mod;
	return ret%mod;
}
ll jx[maxn];
ll C(ll n,ll m)
{
	if(n<m)return 0;
	return jx[n]*quick_pow(jx[m]*jx[n-m]%mod,mod-2)%mod;
}
int N;
int rev[maxn];
ll lim=1,cnt=0;
ll ans=0,f[maxn];
void NTT(ll *a,int n,int opt)
{
	for(int i=0;i<n;i++)
	  if(i<rev[i])
	    swap(a[i],a[rev[i]]);
	for(int mid=1;mid<n;mid<<=1)
	{
		ll Wn=quick_pow(root,(mod-1)/(mid<<1));
		if(opt==-1)Wn=quick_pow(Wn,mod-2);
		for(int i=0;i<n;i+=(mid<<1))
		{
			ll W=1;
			for(int j=0;j<mid;j++,W=(W*Wn)%mod)
			{
				ll u=a[i+j],v=W*a[i+mid+j]%mod;
				a[i+j]=(u+v)%mod,a[i+mid+j]=(u-v+mod)%mod;
			}
		}
	}
	if(opt==-1){ll inv_n=quick_pow(n,mod-2);for(int i=0;i<n;i++)a[i]=a[i]*inv_n%mod;}
	return ;
}
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int main()
{
	freopen("crazy_robot.in","r",stdin);
	freopen("crazy_robot.out","w",stdout);
	N=read();
	memset(f,0,sizeof(f));	
	jx[0]=1;
	for(int i=1;i<=N;i++)jx[i]=i*jx[i-1]%mod;
	while(lim<(N<<1))lim<<=1,cnt++;
	for(int i=0;i<lim;i++)
	  rev[i]=(rev[i>>1]>>1)|((i&1)<<(cnt-1));
	f[0]=1;
	for(int i=1;i<=N;i++)if(!(i&1))f[i]=(C(i,i/2)-C(i,i/2-1))%mod;
	for(int i=0;i<=N;i++)f[i]=f[i]*quick_pow(jx[i],mod-2)%mod;
	NTT(f,lim,1);
	for(int i=0;i<lim;i++)f[i]=f[i]*f[i]%mod;
	NTT(f,lim,-1);
	for(int i=0;i<lim;i++)f[i]=jx[i]*f[i]%mod;
	for(int i=0;i<lim;i++)f[i]=(f[i]*C(N,i))%mod;
	for(int i=0;i<=N;i++)ans=(ans+f[i])%mod;
	printf("%lld\n",ans);
	return 0;
}