Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
32621 | yuanjiabao | 【S】T2 | C++ | 通过 | 100 | 640 MS | 17016 KB | 1179 | 2024-09-15 17:02:53 |
#include<iostream> #include<cstring> using namespace std; #define int long long const int N=310,K=1010,P=998244353; inline int fpow(int a,int b=P-2){ int c=1; for(;b;b>>=1,a=a*a%P)if(b&1)c=c*a%P; return c; } int n,k; int fac[K]; int f[2][K][N],binom[K][K]; void init(){ fac[0]=1; for(int i=1;i<K;i++)fac[i]=fac[i-1]*i%P; for(int i=0;i<K;i++){ binom[i][0]=1; for(int j=1;j<=i;j++)binom[i][j]=(binom[i-1][j-1]+binom[i-1][j])%P; } } signed main(){ // freopen("caged.in","r",stdin); // freopen("caged.out","w",stdout); init(); cin>>n>>k; f[0][0][n]=1; int ans=0; for(int h=1;h<=k;h++){ int invh=fpow(h); for(int s=1;s<=k;s++){ int now=1; for(int lst=1;lst<=n&&lst*h<=s;lst++){ now=now*invh%P; for(int i=lst;i<=n&&i*(h-1)<=s-lst;i++)f[1][s][lst]=(f[1][s][lst]+f[0][s-lst][i]*binom[i][lst]%P*now)%P; if(s==k)ans=(ans+h*f[1][k][lst]%P*fac[k])%P; } } memcpy(f[0],f[1],sizeof(f[0])); memset(f[1],0,sizeof(f[1])); } cout<<ans; return 0; }