Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
32596 A21μΘ_wjy 【S】T2 C++ 通过 100 598 MS 9896 KB 1283 2024-09-15 14:53:55

Tests(44/44):


#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; }


测评信息: