結果
問題 | No.1417 100の倍数かつ正整数(2) |
ユーザー | ygd. |
提出日時 | 2021-03-05 22:00:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 399 ms / 3,000 ms |
コード長 | 1,515 bytes |
コンパイル時間 | 199 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 90,796 KB |
最終ジャッジ日時 | 2024-04-16 09:29:38 |
合計ジャッジ時間 | 6,551 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 45 ms
53,120 KB |
testcase_01 | AC | 45 ms
52,864 KB |
testcase_02 | AC | 115 ms
76,928 KB |
testcase_03 | AC | 43 ms
52,224 KB |
testcase_04 | AC | 45 ms
52,096 KB |
testcase_05 | AC | 43 ms
52,480 KB |
testcase_06 | AC | 44 ms
52,224 KB |
testcase_07 | AC | 44 ms
52,608 KB |
testcase_08 | AC | 44 ms
52,864 KB |
testcase_09 | AC | 45 ms
52,736 KB |
testcase_10 | AC | 45 ms
52,736 KB |
testcase_11 | AC | 44 ms
52,864 KB |
testcase_12 | AC | 64 ms
64,512 KB |
testcase_13 | AC | 68 ms
66,048 KB |
testcase_14 | AC | 73 ms
68,480 KB |
testcase_15 | AC | 86 ms
72,704 KB |
testcase_16 | AC | 104 ms
76,544 KB |
testcase_17 | AC | 108 ms
76,416 KB |
testcase_18 | AC | 117 ms
76,800 KB |
testcase_19 | AC | 119 ms
77,056 KB |
testcase_20 | AC | 122 ms
76,588 KB |
testcase_21 | AC | 129 ms
77,128 KB |
testcase_22 | AC | 130 ms
76,952 KB |
testcase_23 | AC | 129 ms
76,836 KB |
testcase_24 | AC | 122 ms
76,768 KB |
testcase_25 | AC | 127 ms
77,440 KB |
testcase_26 | AC | 127 ms
76,792 KB |
testcase_27 | AC | 137 ms
77,096 KB |
testcase_28 | AC | 129 ms
77,312 KB |
testcase_29 | AC | 126 ms
76,544 KB |
testcase_30 | AC | 202 ms
79,172 KB |
testcase_31 | AC | 179 ms
78,568 KB |
testcase_32 | AC | 260 ms
81,336 KB |
testcase_33 | AC | 259 ms
83,620 KB |
testcase_34 | AC | 388 ms
89,948 KB |
testcase_35 | AC | 390 ms
90,276 KB |
testcase_36 | AC | 399 ms
90,796 KB |
testcase_37 | AC | 299 ms
88,868 KB |
testcase_38 | AC | 257 ms
88,580 KB |
ソースコード
def TWO(X): if X == 8: return 3 elif X == 4: return 2 elif X == 2 or X == 6: return 1 else: return 0 def FIVE(X): if X == 5: return 1 else: return 0 NS = str(input()); MOD = pow(10,9)+7 N = len(NS) #桁数 #dp[i][p][q][j]: i桁目まで見て、2のp乗で割れる、5のq乗で割れる、j=0一致/1以下しているかどうかで dp = [[[[0]*2 for _ in range(3)] for _ in range(3)] for _ in range(N+1)] dp[0][0][0][0] = 1 for i in range(N): for num in range(1,10): #0が一つでもあったらダメなので不要 for p in range(3): for q in range(3): np = min(p + TWO(num),2) nq = min(q + FIVE(num),2) if num == int(NS[i]): #一致している場合 0-> 0 #print("A",i+1,np,nq,p,q) dp[i+1][np][nq][0] += dp[i][p][q][0] dp[i+1][np][nq][0] %= MOD elif num < int(NS[i]): #0 -> 1 #print("B",i+1,np,nq,p,q) dp[i+1][np][nq][1] += dp[i][p][q][0] dp[i+1][np][nq][1] %= MOD dp[i+1][np][nq][1] += dp[i][p][q][1] #1 -> 1 dp[i+1][np][nq][1] %= MOD if i != 0: #最上位以外で np = min(TWO(num),2) nq = min(FIVE(num),2) dp[i+1][np][nq][1] += 1 #print(dp) ans = dp[N][2][2][0] + dp[N][2][2][1] print(ans%MOD)