結果
問題 | No.189 SUPER HAPPY DAY |
ユーザー | fmhr |
提出日時 | 2015-04-23 00:24:46 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 1,754 ms / 5,000 ms |
コード長 | 1,503 bytes |
コンパイル時間 | 325 ms |
コンパイル使用メモリ | 10,900 KB |
実行使用メモリ | 103,984 KB |
最終ジャッジ日時 | 2023-09-18 08:24:21 |
合計ジャッジ時間 | 31,223 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 843 ms
91,820 KB |
testcase_01 | AC | 858 ms
91,936 KB |
testcase_02 | AC | 838 ms
91,972 KB |
testcase_03 | AC | 845 ms
91,912 KB |
testcase_04 | AC | 845 ms
91,840 KB |
testcase_05 | AC | 848 ms
91,844 KB |
testcase_06 | AC | 856 ms
92,132 KB |
testcase_07 | AC | 847 ms
91,808 KB |
testcase_08 | AC | 852 ms
91,896 KB |
testcase_09 | AC | 853 ms
91,900 KB |
testcase_10 | AC | 846 ms
91,808 KB |
testcase_11 | AC | 851 ms
92,032 KB |
testcase_12 | AC | 847 ms
91,936 KB |
testcase_13 | AC | 1,268 ms
97,792 KB |
testcase_14 | AC | 1,447 ms
100,064 KB |
testcase_15 | AC | 1,485 ms
101,084 KB |
testcase_16 | AC | 1,604 ms
102,904 KB |
testcase_17 | AC | 1,639 ms
103,196 KB |
testcase_18 | AC | 1,462 ms
100,428 KB |
testcase_19 | AC | 1,705 ms
103,984 KB |
testcase_20 | AC | 1,088 ms
95,112 KB |
testcase_21 | AC | 1,083 ms
94,672 KB |
testcase_22 | AC | 855 ms
92,144 KB |
testcase_23 | AC | 1,285 ms
97,756 KB |
testcase_24 | AC | 1,338 ms
97,628 KB |
testcase_25 | AC | 1,754 ms
103,744 KB |
ソースコード
M, D = map(int, input().split()) MOD = 1000000009 Msz = len(str(M)) Dsz = len(str(D)) MAX = max(Msz, Dsz) last_max = sum(int(_) for _ in list(str(M))) def dp(p): sz = len(str(p)) dp = [[[0 for f in range(2)] for a in range(2005)] for b in range(205)] dp[0][0][0] = 1 for i in range(sz): num = int(str(p)[-1-i]) for j in range(2000): for l in range(2): if dp[i][j][l] == 0: continue dp[i][j][l] %= MOD for k in range(10): if k<num: dp[i + 1][j + k][0] += dp[i][j][l] elif k>num: dp[i + 1][j + k][1] += dp[i][j][l] else: dp[i + 1][j + k][l] += dp[i][j][l] return dp dp1 = dp(M) dp2 = dp(D) ans = 0 # for i in range(M_x): # for j in range(D_x): # for x in range(MAX*9): # ans += dp1[i][x][0] * dp2[j][x][0] # print(dp1[i][x][0] * dp2[j][x][0]) d1 = [0] * 2000 d2 = [0] * 2000 for i in range(MAX*9+2): d1[i] = dp1[Msz][i][0] % MOD d2[i] = dp2[Dsz][i][0] % MOD for i in range(MAX*9+2): ans += d1[i] * d2[i] ans %= MOD print(ans%MOD-1) # # M_set = [0] # D_set = [0] # for i in range(1, M+1): # M_set.append(sum_of_digit(i)) # for j in range(1, D+1): # D_set.append(sum_of_digit(j)) # # M_set = set(M_set) # D_set = set(D_set) # ans = M_set & D_set # # print(len(ans) % 1000000009) # print(M_set)