C++(g++ 7.5.0) 解法, 执行用时: 801ms, 内存消耗: 7824K, 提交时间: 2023-01-13 21:43:58

//分治fft板子
//f[n] =(1<=i<=n-1) g[i]*f[n-i]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=4e5+77,mod=998244353,G=3;
int lg=0,len=1;

ll fac[N];
ll a[N],b[N],g[N],f[N];
int rev[N];

ll power(ll x,ll t)
{
	ll b=1;
	while(t)
	{
		if(t&1) b=b*x%mod;
		x=x*x%mod; t>>=1;
	}
	return b;
}
void dft(ll *a,int n,int aii)
{
	for(int i=0; i<n; i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int i=2; i<=n; i<<=1)
	{
		int now=i>>1;
		ll wn=power(G,(mod-1)/i);
		if(aii==-1) wn=power(wn,mod-2);
		for(int j=0; j<n; j+=i)
		{
			ll w=1,x,y;
			for(int k=j; k<j+now; k++,w=w*wn%mod)
			{
				x=a[k],y=w*a[k+now]%mod;
				a[k]=(x+y)%mod; a[k+now]=(x-y+mod)%mod;
			}
		}
	}
	if(aii==-1) for(int i=0; i<=n; i++) a[i]=a[i]*power(n,mod-2)%mod;
}
void NTT(ll *a,ll *b,int n,int m)
{
	dft(a,len,1); dft(b,len,1);
	for(int i=0; i<=len; i++) a[i]=a[i]*b[i]%mod;
	dft(a,len,-1);
}
void cdq(int l,int r)
{
	if(l==r) return;
	int mid=(l+r)>>1;
	cdq(l,mid);
	int n=r-l+1; len=1; lg=0;
	while(len<=n)
	{
		len<<=1; lg++;
	}
	for(int i=0; i<len; i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1)),a[i]=b[i]=0;
	for(int i=l; i<=mid; i++) a[i-l]=((fac[i]-f[i])+mod)%mod;
	for(int i=1; i<=r-l; i++) b[i-1]=fac[i];
	NTT(a,b,mid-l+1,r-l);
	for(int i=mid+1; i<=r; i++) f[i]=(f[i]+a[i-l-1])%mod;
	cdq(mid+1,r);
}
int n;
int main()
{
	int maxn=400005;
    fac[0]=1;
    for(int i=1;i<=maxn;++i)fac[i]=fac[i-1]*i%mod;
	fac[0]=0;//方便卷积 
	int T;
	scanf("%d", &T);
	cdq(0, 100005);
	while(T--) 
	{
		scanf("%d",&n);
		printf("%lld\n", (f[n]+mod)%mod);
	}
} 

C++11(clang++ 3.9) 解法, 执行用时: 164ms, 内存消耗: 4968K, 提交时间: 2018-11-30 20:08:04

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <iostream>
#include <bitset>
using namespace std;
#define N 100005
#define ll long long
#define mod 998244353
int q_pow(int x,int n){int ret=1;for(;n;n>>=1,x=(ll)x*x%mod)if(n&1)ret=(ll)ret*x%mod;return ret;}
#define inv(x) q_pow(x,mod-2)
int A[N<<2],B[N<<2],n,a[N<<2],b[N<<2];
void NTT(int *a,int len,int flag)
{
	int i,j,k,t,w,x,tmp;
	for(i=k=0;i<len;i++)
	{
		if(i>k)swap(a[i],a[k]);
		for(j=len>>1;(k^=j)<j;j>>=1);
	}
	for(k=2;k<=len;k<<=1)
	{
		t=k>>1;x=q_pow(3,(mod-1)/k);if(flag==-1)x=inv(x);
		for(i=0;i<len;i+=k)
			for(w=1,j=i;j<i+t;j++)
			{
				tmp=(ll)a[j+t]*w%mod;
				a[j+t]=(a[j]-tmp+mod)%mod;a[j]=(a[j]+tmp)%mod;
				w=(ll)w*x%mod;
			}
	}if(flag==-1)for(t=inv(len),i=0;i<len;i++)a[i]=(ll)t*a[i]%mod;
}
void get_inv(int *a,int *b,int len)
{
	if(len==1){b[0]=q_pow(a[0],mod-2);return ;}
	get_inv(a,b,len>>1);int tt=len<<1;
	for(int i=0;i<len;i++)A[i]=a[i],B[i]=b[i];
	NTT(A,tt,1);NTT(B,tt,1);
	for(int i=0;i<tt;i++)A[i]=(ll)A[i]*B[i]%mod*B[i]%mod;
	NTT(A,tt,-1);
	for(int i=0;i<=n;i++)b[i]=((b[i]<<1)%mod-A[i]+mod)%mod;
	for(int i=len+1;i<tt;i++)b[i]=0;
}
int main()
{
	n=100000;a[0]=1;
	for(int i=1;i<=n;i++)a[i]=(ll)a[i-1]*i%mod;a[0]=1;
	int len=1;while(len<=n)len<<=1;
	get_inv(a,b,len);
    int T;scanf("%d",&T);
    while(T--)scanf("%d",&n),printf("%d\n",(a[n]+b[n])%mod);
}