結果
| 問題 | No.1417 100の倍数かつ正整数(2) |
| ユーザー |
 U S
|
| 提出日時 | 2021-03-05 23:06:20 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 353 ms / 3,000 ms |
| コード長 | 4,828 bytes |
| コンパイル時間 | 161 ms |
| コンパイル使用メモリ | 82,260 KB |
| 実行使用メモリ | 93,772 KB |
| 最終ジャッジ日時 | 2024-10-07 04:36:04 |
| 合計ジャッジ時間 | 6,275 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 55 ms
63,424 KB |
| testcase_01 | AC | 54 ms
65,768 KB |
| testcase_02 | AC | 116 ms
78,256 KB |
| testcase_03 | AC | 51 ms
62,948 KB |
| testcase_04 | AC | 52 ms
63,000 KB |
| testcase_05 | AC | 51 ms
63,196 KB |
| testcase_06 | AC | 50 ms
62,624 KB |
| testcase_07 | AC | 54 ms
62,932 KB |
| testcase_08 | AC | 53 ms
63,840 KB |
| testcase_09 | AC | 51 ms
62,932 KB |
| testcase_10 | AC | 52 ms
62,796 KB |
| testcase_11 | AC | 51 ms
63,544 KB |
| testcase_12 | AC | 68 ms
72,168 KB |
| testcase_13 | AC | 79 ms
74,728 KB |
| testcase_14 | AC | 88 ms
77,328 KB |
| testcase_15 | AC | 96 ms
77,432 KB |
| testcase_16 | AC | 105 ms
77,456 KB |
| testcase_17 | AC | 111 ms
77,976 KB |
| testcase_18 | AC | 124 ms
78,204 KB |
| testcase_19 | AC | 104 ms
77,604 KB |
| testcase_20 | AC | 129 ms
78,400 KB |
| testcase_21 | AC | 110 ms
77,620 KB |
| testcase_22 | AC | 155 ms
78,940 KB |
| testcase_23 | AC | 145 ms
78,248 KB |
| testcase_24 | AC | 121 ms
77,904 KB |
| testcase_25 | AC | 160 ms
78,844 KB |
| testcase_26 | AC | 111 ms
77,636 KB |
| testcase_27 | AC | 129 ms
78,056 KB |
| testcase_28 | AC | 156 ms
78,676 KB |
| testcase_29 | AC | 137 ms
78,544 KB |
| testcase_30 | AC | 183 ms
80,128 KB |
| testcase_31 | AC | 146 ms
79,456 KB |
| testcase_32 | AC | 251 ms
82,436 KB |
| testcase_33 | AC | 197 ms
85,684 KB |
| testcase_34 | AC | 257 ms
92,088 KB |
| testcase_35 | AC | 257 ms
92,608 KB |
| testcase_36 | AC | 258 ms
92,732 KB |
| testcase_37 | AC | 353 ms
93,772 KB |
| testcase_38 | AC | 257 ms
92,660 KB |
ソースコード
# import sys
# input = sys.stdin.readline
def mp():return map(int,input().split())
def lmp():return list(map(int,input().split()))
import math
import bisect
from copy import deepcopy as dc
from itertools import accumulate
from collections import Counter, defaultdict, deque
def ceil(U,V):return (U+V-1)//V
def modf1(N,MOD):return (N-1)%MOD+1
inf = int(1e30)
mod = int(1e9+7)
n = input()
nb = [n[0]]
now = n[0]
for i in range(1,len(n)):
if now != "0":
now = n[i]
nb.append(now)
else:nb.append(now)
n = "".join(nb)
dp0 = [[[[0]*3 for j in range(3)] for i in range(len(n)+1)] for v in range(2)]
dp1 = [[[[0]*3 for j in range(3)] for i in range(len(n)+1)] for v in range(2)]
dp0[0][0][0][0] = 1
for v in range(2):
for i in range(len(n)):
for j in range(3):
for k in range(3):
for l in range(10):
if l > int(n[i]):
if l == 2 or l == 6:
dp1[1][i+1][min(2,j+1)][k] += dp1[v][i][j][k]
dp1[1][i + 1][min(2, j + 1)][k] %= mod
elif l == 5:
dp1[1][i+1][j][min(2,k+1)] += dp1[v][i][j][k]
dp1[1][i + 1][j][min(2, k + 1)] %= mod
elif l == 4 or l == 8:
dp1[1][i+1][2][k] += dp1[v][i][j][k]
dp1[1][i + 1][2][k] %= mod
else:
dp1[1][i+1][j][k] += dp1[v][i][j][k]
dp1[1][i + 1][j][k] %= mod
elif l == int(n[i]):
if l == 2 or l == 6:
dp0[1][i+1][min(2,j+1)][k] += dp0[v][i][j][k]
dp0[1][i + 1][min(2, j + 1)][k] %= mod
dp1[1][i+1][min(2,j+1)][k] += dp1[v][i][j][k]
dp1[1][i + 1][min(2, j + 1)][k] %= mod
elif l == 5:
dp0[1][i + 1][j][min(2, k + 1)] += dp0[v][i][j][k]
dp0[1][i + 1][j][min(2, k + 1)] %= mod
dp1[1][i+1][j][min(2,k+1)] += dp1[v][i][j][k]
dp1[1][i + 1][j][min(2, k + 1)] %= mod
elif l == 4 or l == 8:
dp0[1][i+1][2][k] += dp0[v][i][j][k]
dp0[1][i + 1][2][k] %= mod
dp1[1][i+1][2][k] += dp1[v][i][j][k]
dp1[1][i + 1][2][k] %= mod
elif l == 0:
if v == 0:
dp1[0][i+1][j][k] += dp0[0][i][j][k]
dp1[0][i + 1][j][k] %= mod
dp1[0][i+1][j][k] += dp1[0][i][j][k]
dp1[0][i + 1][j][k] %= mod
else:
dp0[1][i+1][j][k] += dp0[v][i][j][k]
dp0[1][i + 1][j][k] %= mod
dp1[1][i+1][j][k] += dp1[v][i][j][k]
dp1[1][i + 1][j][k] %= mod
else:
if l == 2 or l == 6:
dp1[1][i+1][min(2,j+1)][k] += dp0[v][i][j][k]
dp1[1][i + 1][min(2, j + 1)][k] %= mod
dp1[1][i+1][min(2,j+1)][k] += dp1[v][i][j][k]
dp1[1][i + 1][min(2, j + 1)][k] %= mod
elif l == 5:
dp1[1][i + 1][j][min(2, k + 1)] += dp0[v][i][j][k]
dp1[1][i + 1][j][min(2, k + 1)] %= mod
dp1[1][i+1][j][min(2,k+1)] += dp1[v][i][j][k]
dp1[1][i + 1][j][min(2, k + 1)] %= mod
elif l == 4 or l == 8:
dp1[1][i+1][2][k] += dp0[v][i][j][k]
dp1[1][i + 1][2][k] %= mod
dp1[1][i+1][2][k] += dp1[v][i][j][k]
dp1[1][i + 1][2][k] %= mod
elif l == 0:
if v == 0:
dp1[0][i+1][j][k] += dp0[0][i][j][k]
dp1[0][i + 1][j][k] %= mod
dp1[0][i+1][j][k] += dp1[0][i][j][k]
dp1[0][i + 1][j][k] %= mod
else:
dp1[1][i+1][j][k] += dp0[v][i][j][k]
dp1[1][i + 1][j][k] %= mod
dp1[1][i+1][j][k] += dp1[v][i][j][k]
dp1[1][i + 1][j][k] %= mod
print((dp0[0][len(n)][2][2] + dp1[0][len(n)][2][2] + dp0[1][len(n)][2][2] + dp1[1][len(n)][2][2])%mod)