#include<bits/stdc++.h>
#define psb push_back
#define fi first
#define se second
#define endl '\n'
#define int long long
using namespace std;
const int N=2e5+5,mod=998244353;
int n,f[N<<1],ans,fac[N<<1],inv[N<<1];
namespace math{
	int pmod(int a){while(a>=mod)a-=mod;while(a<0)a+=mod;return a;} 
	void add(int &a,int b){a=pmod(a+b);}
	int qpow(int a,int b){
		int res=1;
		for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)res=1ll*res*a%mod;
		return res;
	}
	int Inv(int a){return qpow(a,mod-2);}
}
namespace Poly{
	using poly=vector<int>;
	using namespace math;
	const int G=3,invG=Inv(3);
	void ntt(poly &a,int op=1){
		int n=a.size();
		static vector<int> rv;static int lsn;
		if(lsn!=n){
			rv.resize(n);
			for(int i=1;i<n;i++)rv[i]=rv[i>>1]>>1|((i&1)?(n>>1):0);
		}
		for(int i=0;i<n;i++)if(rv[i]<i)swap(a[rv[i]],a[i]);
		for(int k=1,x=2;x<=n;x<<=1,k<<=1){
			int Gn=qpow(op==1?G:invG,(mod-1)/x);
			for(int i=0;i<n;i+=x){
				int g=1;
				for(int j=0;j<k;j++,g=1ll*g*Gn%mod){
					int t1=a[i+j],t2=1ll*g*a[i+j+k]%mod;
					a[i+j]=pmod(t1+t2);
					a[i+j+k]=pmod(t1-t2);
				}
			}
		}
		if(op==-1){
			int iv=Inv(n);
			for(int &i:a)i=1ll*i*iv%mod;
		}
	}
	poly operator*(poly a,poly b){
		int n=a.size()+b.size()-1,len=1<<__lg(n*2-1); 
		a.resize(len),b.resize(len);
		ntt(a),ntt(b);
		poly res(len);
		for(int i=0;i<len;i++)res[i]=1ll*a[i]*b[i]%mod;
		ntt(res,-1),res.resize(n);
		return res;
	}
}
using Poly::poly;using Poly::operator*;using namespace math;
poly g;
int C(int n,int m){return m>n||m<0?0:fac[n]*inv[m]%mod*inv[n-m]%mod;}
void solve(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1;
	solve(l,mid);
	poly tmp=poly(f+l,f+mid+1)*poly(g.begin(),g.begin()+r-l+1);
	for(int i=mid+1;i<=r;i++)add(f[i],-tmp[i-l]);
	solve(mid+1,r);
}
signed main(){
//	freopen("walk.in","r",stdin);
//	freopen("walk.out","w",stdout); 
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	fac[0]=1;
	for(int i=1;i<=n<<1;i++)fac[i]=fac[i-1]*i%mod;
	inv[n<<1]=qpow(fac[n<<1],mod-2);
	for(int i=n<<1;i>=1;i--)inv[i-1]=inv[i]*i%mod;
	g.resize(n+1);
	for(int i=0;i<=n;i+=2)g[i]=C(i,i/2),f[i]=C(i+n,i/2);
	solve(0,n);
	int ans=0;
	for(int i=0;i<=n;i++)add(ans,f[i]);
	cout<<ans<<endl;
	return 0;
}

洛谷

满级模拟

经典永流传

新时代神贴

image](/file/8595/8e-7ArsBTxmzsrausdRrW.png)

STL大法好(

map<queue<priority_queue<vector<set<list<multiset<multimap<int,stack<int>>>>>>>>,deque<set<pair<bitset<64>,unordered_map<int,unordered_set<int>>>>::iterator>>mp;

临时代码区