結果
問題 |
No.189 SUPER HAPPY DAY
|
ユーザー |
![]() |
提出日時 | 2022-05-31 06:33:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,023 ms / 5,000 ms |
コード長 | 716 bytes |
コンパイル時間 | 335 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 86,752 KB |
最終ジャッジ日時 | 2024-09-21 01:06:16 |
合計ジャッジ時間 | 11,380 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
# 桁DP。 # 下の桁で場合分けする方針でAC。 # X=10x+yとおいて考えれば良いのだが、自力では思い出せず検索してしまった。 M,D=map(int,input().split()) mod=10**9+9 from functools import lru_cache @lru_cache(maxsize=None) def calc(X): ANS=[0]*2000 if X<=9: for i in range(X+1): ANS[i]=1 return ANS for i in range(10): if X>=i: x=(X-i)//10 for j in range(2000): if calc(x)[j]!=0: ANS[j+i]+=calc(x)[j] ANS[j+i]%=mod return ANS ANS=calc(M) ANS2=calc(D) score=0 for i in range(1,2000): score+=ANS[i]*ANS2[i] score%=mod print(score)