Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
32631 | liuyile | 【S】T2 | C++ | 运行超时 | 65 | 1000 MS | 14516 KB | 1370 | 2024-09-15 20:23:09 |
#include <bits/stdc++.h> using namespace std; #define int long long int n,k; int f[2][1010][310]; const int M=998244353; inline int qp(int a,int x){ int res=1; while(x){ if(x&1)res=res*a%M; a=a*a%M; x>>=1; } return res; } inline int inv(int x){return qp(x,M-2);} int C[1010][1010]; inline void add(int &x,int y){ x+=y; if(x>=M)x-=M; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("genshin.in","r",stdin); // freopen("caged.out","w",stdout); C[0][0]=1; for(int i=1;i<=1000;i++){ C[i][0]=1; for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%M; } cin>>n>>k; f[0][0][n]=1; bool fl=0; int res=0; for(int i=0;i<k;i++){ fl^=1; // cout<<i<<" "; // cout.flush(); memset(f[fl],0,sizeof(f[fl])); int t=inv(i+1); for(int j=0;j<=k;j++) for(int p=1;i*p<=j&&p<=n;p++){ int buf=1; for(int q=1;q<=p&&j+q<=k;q++) buf=buf*t%M,add(f[fl][j+q][q],f[!fl][j][p]*C[p][q]%M*buf%M); } for(int j=1;j<=n;j++) add(res,(i+1)*f[fl][k][j]%M); } for(int i=1;i<=k;i++) res=res*i%M; cout<<res<<endl; cout.flush(); return 0; }