結果
問題 |
No.189 SUPER HAPPY DAY
|
ユーザー |
![]() |
提出日時 | 2022-11-04 21:35:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 619 ms / 5,000 ms |
コード長 | 1,075 bytes |
コンパイル時間 | 173 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 105,856 KB |
最終ジャッジ日時 | 2024-07-18 19:18:03 |
合計ジャッジ時間 | 7,358 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
import sys import itertools import heapq import bisect from collections import deque, defaultdict from functools import lru_cache, cmp_to_key input = sys.stdin.readline # for AtCoder Easy test if __file__ != 'prog.py': sys.setrecursionlimit(10 ** 6) def readints(): return map(int, input().split()) def readlist(): return list(readints()) def readstr(): return input().rstrip() M, D = input().split() mod = 10 ** 9 + 9 def solve(n): dp = [[0, 0] for _ in range(L + 1)] dp[0][0] = 1 for i in range(len(n)): ndp = [[0, 0] for _ in range(L + 1)] for j in range(L + 1): for k in range(10): if j - k < 0: break ndp[j][1] += dp[j - k][1] if k < int(n[i]): ndp[j][1] += dp[j - k][0] elif k == int(n[i]): ndp[j][0] += dp[j - k][0] dp = ndp return dp L = 2000 dpm = solve(M) dpd = solve(D) ans = 0 for i in range(1, L + 1): ans += sum(dpm[i]) * sum(dpd[i]) % mod ans %= mod print(ans)