提交时间:2024-09-15 18:06:53
运行 ID: 32622
#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define p_b push_back #define m_p make_pair #define ppc __builtin_popcount using namespace std; typedef long long ll; const int maxn=1e6+10; const ll mod=998244353; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; }int n,k,jc[5005],jc_inv[5005],f[1005][1005],ret[1005],dp[2][305][1005]; int qpow(int a,int b){ int res=1; while(b){ if(b&1)res=res*1ll*a%mod; a=a*1ll*a%mod;b>>=1; }return res; } ll A(int n,int m){return jc[m]*1ll*jc_inv[m-n]%mod;} ll C(int n,int m){return jc[m]*1ll*jc_inv[m-n]%mod*1ll*jc_inv[n]%mod;} void init(){ jc[0]=jc_inv[0]=1;up(i,1,5000)jc[i]=jc[i-1]*1ll*i%mod,jc_inv[i]=qpow(jc[i],mod-2); up(i,0,1000)up(j,0,1000)f[i][j]=qpow(jc_inv[i],j); } void slv(){ n=read(),k=read();init(); dp[0][n][0]=1; int res=0; up(i,1,k){ int op=i&1; memset(dp[op],0,sizeof(dp[op])); up(j,0,n){ up(w,(i-1)*j,min((i-1)*n,k)){ if(!dp[!op][j][w])continue; up(o,1,min(k-w,j)){ (dp[op][o][w+o]+=dp[!op][j][w]*1ll*C(o,j)%mod*1ll*f[i-1][j-o]%mod)%=mod; } } }up(j,1,n)(res+=dp[op][j][k]*1ll*f[i][j]%mod*1ll*i%mod)%=mod; //cout<<"? "<<res<<"\n"; }cout<<res*1ll*jc[k]%mod; }int main(){ //freopen("caged.in","r",stdin); //freopen("caged.out","w",stdout); slv(); //cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; fclose(stdin); fclose(stdout); return 0; }