結果
問題 | No.2951 Similar to Mex |
ユーザー |
|
提出日時 | 2024-10-21 23:14:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 354 ms / 2,000 ms |
コード長 | 773 bytes |
コンパイル時間 | 268 ms |
コンパイル使用メモリ | 82,388 KB |
実行使用メモリ | 97,908 KB |
最終ジャッジ日時 | 2024-10-25 20:51:44 |
合計ジャッジ時間 | 9,726 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
N,M,K=map(int,input().split()) T=max(M,K)+1 mod=998244353 dp=[[0]*(T+1) for i in range(N+1)] dp[0][0]=1 for i in range(1,T+1): ndp=[[0]*(T+1)for i in range(N+1)] for k in range(i): tmp=pow(i,max(0,min(i,K)-k),mod) for j in range(min(i,N+1)): if i<=M and j<N: ndp[j+1][k]=(ndp[j+1][k]+dp[j][k])%mod ndp[j][i]=(ndp[j][i]+dp[j][k]*tmp)%mod dp,ndp=ndp,dp S=[[0]*(N+1)for i in range(N+1)] S[0][0]=1 for i in range(N): for j in range(i+1): S[i+1][j]=(S[i+1][j]+S[i][j]*j)%mod S[i+1][j+1]=(S[i+1][j+1]+S[i][j])%mod fac=[0]*(N+1) fac[0]=1 for i in range(1,N+1):fac[i]=(i*fac[i-1])%mod ans=0 for i in range(1,N+1): ans=(ans+dp[i][T]*S[N][i]%mod*fac[i])%mod print(ans)