Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
32594 | A21μΘ_wjy | 【S】T2 | C++ | 解答错误 | 0 | 1000 MS | 7492 KB | 1133 | 2024-09-15 14:50:48 |
#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]; signed main(){ Gfac(); cin>>n>>k; 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&&i*p<=k;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]*qpow(qpow(i,mod-2),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; }