結果
問題 | No.1417 100の倍数かつ正整数(2) |
ユーザー |
|
提出日時 | 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 |
ソースコード
# 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)