提交时间:2024-09-15 14:53:55
运行 ID: 32596
#include<bits/stdc++.h> #define int long long using namespace std; const int mod=998244353; const int maxn=307; const int maxk=1007; int n,k; inline int qpow(int a,int b){ int ans=1; while(b){ if(b&1)ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } int fac[maxk],ifac[maxk]; inline void Gfac(){ fac[0]=1; for(int i=1;i<maxk;i++)fac[i]=fac[i-1]*i%mod; ifac[maxk-1]=qpow(fac[maxk-1],mod-2); for(int i=maxk-2;i>=0;i--)ifac[i]=ifac[i+1]*(i+1)%mod; } inline int C(int n,int m){ if(n<0||m<0||n<m)return 0; return fac[n]*ifac[m]%mod*ifac[n-m]%mod; } int dp[2][maxk][maxn]; int IP[maxk][maxn]; inline int GIP(){ for(int i=1;i<=k;i++){ int c=qpow(i,mod-2); IP[i][0]=1; for(int j=1;j<=n;j++)IP[i][j]=IP[i][j-1]*c%mod; } } signed main(){ cin>>n>>k; Gfac(); GIP(); dp[0][0][n]=1; int f=0; int ans=0; for(int i=1;i<=k;i++){ memset(dp[!f],0,sizeof(dp[!f])); for(int j=0;j<=k;j++){ for(int p=1;p<=n;p++){ if(!dp[f][j][p])continue; for(int q=1;q<=min(p,k-j);q++){ dp[!f][j+q][q]+=dp[f][j][p]*IP[i][q]%mod*C(p,q)%mod; dp[!f][j+q][q]-=(dp[!f][j+q][q]>=mod?mod:0); } } } f=!f; for(int p=1;p<=n;p++)ans=(ans+dp[f][k][p]*i)%mod; } ans=ans*fac[k]%mod; cout<<ans<<endl; }