結果
| 問題 | No.1417 100の倍数かつ正整数(2) |
| ユーザー |
 U S
|
| 提出日時 | 2021-03-05 23:06:20 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 334 ms / 3,000 ms |
| コード長 | 4,828 bytes |
| コンパイル時間 | 197 ms |
| コンパイル使用メモリ | 82,816 KB |
| 実行使用メモリ | 93,468 KB |
| 最終ジャッジ日時 | 2024-04-16 11:05:13 |
| 合計ジャッジ時間 | 5,977 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 55 ms
62,208 KB |
| testcase_01 | AC | 56 ms
64,256 KB |
| testcase_02 | AC | 117 ms
78,024 KB |
| testcase_03 | AC | 51 ms
61,696 KB |
| testcase_04 | AC | 53 ms
62,336 KB |
| testcase_05 | AC | 48 ms
62,720 KB |
| testcase_06 | AC | 50 ms
62,592 KB |
| testcase_07 | AC | 50 ms
62,208 KB |
| testcase_08 | AC | 51 ms
62,080 KB |
| testcase_09 | AC | 49 ms
62,848 KB |
| testcase_10 | AC | 49 ms
62,592 KB |
| testcase_11 | AC | 48 ms
62,208 KB |
| testcase_12 | AC | 64 ms
70,400 KB |
| testcase_13 | AC | 70 ms
74,624 KB |
| testcase_14 | AC | 89 ms
77,440 KB |
| testcase_15 | AC | 91 ms
77,224 KB |
| testcase_16 | AC | 103 ms
77,312 KB |
| testcase_17 | AC | 110 ms
77,908 KB |
| testcase_18 | AC | 117 ms
78,368 KB |
| testcase_19 | AC | 101 ms
77,608 KB |
| testcase_20 | AC | 123 ms
78,408 KB |
| testcase_21 | AC | 105 ms
77,644 KB |
| testcase_22 | AC | 150 ms
78,816 KB |
| testcase_23 | AC | 139 ms
78,336 KB |
| testcase_24 | AC | 114 ms
78,188 KB |
| testcase_25 | AC | 154 ms
78,856 KB |
| testcase_26 | AC | 107 ms
77,380 KB |
| testcase_27 | AC | 123 ms
78,208 KB |
| testcase_28 | AC | 148 ms
78,852 KB |
| testcase_29 | AC | 131 ms
78,820 KB |
| testcase_30 | AC | 181 ms
80,016 KB |
| testcase_31 | AC | 142 ms
79,488 KB |
| testcase_32 | AC | 236 ms
82,184 KB |
| testcase_33 | AC | 183 ms
85,792 KB |
| testcase_34 | AC | 247 ms
92,092 KB |
| testcase_35 | AC | 245 ms
93,000 KB |
| testcase_36 | AC | 247 ms
92,860 KB |
| testcase_37 | AC | 334 ms
93,468 KB |
| testcase_38 | AC | 249 ms
92,528 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)