結果
問題 | No.2951 Similar to Mex |
ユーザー | ゼット |
提出日時 | 2024-10-25 22:52:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 839 ms / 2,000 ms |
コード長 | 1,288 bytes |
コンパイル時間 | 363 ms |
コンパイル使用メモリ | 82,356 KB |
実行使用メモリ | 302,664 KB |
最終ジャッジ日時 | 2024-10-25 22:52:33 |
合計ジャッジ時間 | 24,867 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 182 ms
78,800 KB |
testcase_01 | AC | 183 ms
79,068 KB |
testcase_02 | AC | 211 ms
80,560 KB |
testcase_03 | AC | 229 ms
81,208 KB |
testcase_04 | AC | 191 ms
79,776 KB |
testcase_05 | AC | 203 ms
81,456 KB |
testcase_06 | AC | 198 ms
80,172 KB |
testcase_07 | AC | 202 ms
80,588 KB |
testcase_08 | AC | 192 ms
79,512 KB |
testcase_09 | AC | 186 ms
79,048 KB |
testcase_10 | AC | 197 ms
80,088 KB |
testcase_11 | AC | 365 ms
139,440 KB |
testcase_12 | AC | 623 ms
298,100 KB |
testcase_13 | AC | 414 ms
200,376 KB |
testcase_14 | AC | 495 ms
189,912 KB |
testcase_15 | AC | 689 ms
263,960 KB |
testcase_16 | AC | 459 ms
192,232 KB |
testcase_17 | AC | 555 ms
245,104 KB |
testcase_18 | AC | 586 ms
257,732 KB |
testcase_19 | AC | 422 ms
155,684 KB |
testcase_20 | AC | 555 ms
248,908 KB |
testcase_21 | AC | 528 ms
204,512 KB |
testcase_22 | AC | 563 ms
218,152 KB |
testcase_23 | AC | 692 ms
296,800 KB |
testcase_24 | AC | 623 ms
241,828 KB |
testcase_25 | AC | 740 ms
268,684 KB |
testcase_26 | AC | 572 ms
242,976 KB |
testcase_27 | AC | 827 ms
302,604 KB |
testcase_28 | AC | 770 ms
289,964 KB |
testcase_29 | AC | 815 ms
302,608 KB |
testcase_30 | AC | 813 ms
298,292 KB |
testcase_31 | AC | 786 ms
293,728 KB |
testcase_32 | AC | 820 ms
301,216 KB |
testcase_33 | AC | 794 ms
298,684 KB |
testcase_34 | AC | 806 ms
302,556 KB |
testcase_35 | AC | 839 ms
302,376 KB |
testcase_36 | AC | 183 ms
78,952 KB |
testcase_37 | AC | 184 ms
79,064 KB |
testcase_38 | AC | 182 ms
78,796 KB |
testcase_39 | AC | 645 ms
302,316 KB |
testcase_40 | AC | 536 ms
302,196 KB |
testcase_41 | AC | 552 ms
302,328 KB |
testcase_42 | AC | 633 ms
302,664 KB |
testcase_43 | AC | 643 ms
302,232 KB |
testcase_44 | AC | 727 ms
302,444 KB |
ソースコード
N,M,K=map(int,input().split()) #dp[i][j][k] 数字iまで見た、j種類使用、溜め込みk個 X=max(N,M,K) dp=[[[0]*(X+1) for j in range(X+1)] for i in range(X+2)] dp[0][0][0]=1 v=[[1]*(X+1) for i in range(X+2)] mod=998244353 for i in range(X+2): for j in range(1,X+1): v[i][j]=v[i][j-1]*i v[i][j]%=mod for i in range(X+1): for j in range(i+1): for k in range(i+1): if dp[i][j][k]==0: continue if i<M: if i<K: dp[i+1][j+1][k+1]+=dp[i][j][k] dp[i+1][j+1][k+1]%=mod else: dp[i+1][j+1][k]+=dp[i][j][k] dp[i+1][j+1][k]%=mod if i<K: dp[i+1][j][0]+=dp[i][j][k]*v[i+1][k+1] dp[i+1][j][0]%=mod else: dp[i+1][j][0]+=dp[i][j][k]*v[i+1][k] dp[i+1][j][0]%=mod u=[1]*(2*10**5) for i in range(1,2*10**5): u[i]=u[i-1]*i u[i]%=mod u2=[1]*(2*10**5) for i in range(1,2*10**5): u2[i]=pow(u[i],-1,mod) def ncm(x,y): ans=u[x]*u2[y] ans%=mod ans*=u2[x-y] ans%=mod return ans result=0 q=[[0]*(N+1) for i in range(N+1)] q[0][0]=1 for i in range(N): for j in range(i,N): for k in range(1,N+1): if j+k>N: break q[i+1][j+k]+=q[i][j]*ncm(N-j,k) q[i+1][j+k]%=mod result+=dp[X+1][i+1][0]*q[i+1][N] result%=mod print(result)