結果

問題 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 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)
0