提交时间:2026-04-11 20:46:58
运行 ID: 41253
#include<bits/stdc++.h> using namespace std; const int N=1e4+10; const int mod=998244353; int qp(int a,int b){ int x=1; for(;b;b>>=1,a=1ll*a*a%mod)if(b&1) x=1ll*x*a%mod; return x; } int n,k; int fac[N],ifac[N],c[N*2]; int f[2][N*2],g[2][N],ans[N]; inline void rec(int &x){(x>=mod)?(x-=mod):0;} int main(){ //freopen("count.in","r",stdin); //freopen("count.out","w",stdout); cin>>n>>k; fac[0]=1; for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod; ifac[n]=qp(fac[n],mod-2); for(int i=n-1;i>=0;i--) ifac[i]=1ll*ifac[i+1]*(i+1)%mod; const int iv2=qp(2,mod-2); f[0][0]=1;g[0][0]=1; for(int i=1;i<=n*2;i++) c[i]=1ll*i*(i-1)*iv2%mod; for(int i=1;i<=n;i++){ int w=0;int o=i&1; for(int j=2;j<=i*2;j++){ f[o][j]=(1ll*f[!o][j-2]+2ll*f[!o][j-1]+1ll*f[!o][j])*c[j]%mod; /*(1ll*f[!o][j-2]*j*(j-1)%mod*iv2+ 1ll*f[!o][j-1]*j*(j-1)+ 1ll*f[!o][j]*j*(j-1)%mod*iv2)%mod;*/ rec(w+=f[o][j]); //cout<<i<<' '<<j<<' '<<f[i][j]<<endl; } for(int j=1;j<=i;j++){ g[o][j]=(1ll*g[!o][j]*j+g[!o][j-1])%mod; }f[!o][0]=0;g[!o][0]=0; w=qp(w,k); ans[i]=w; for(int j=1;j<i;j++){ rec(ans[i]+=mod-1ll*g[o][j]*ans[j]%mod); } cout<<1ll*ans[i]*ifac[i]%mod<<'\n'; } return 0; }