結果

問題 No.1417 100の倍数かつ正整数(2)
ユーザー ntuda
提出日時 2025-07-12 13:58:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,709 bytes
コンパイル時間 416 ms
コンパイル使用メモリ 82,332 KB
実行使用メモリ 81,396 KB
最終ジャッジ日時 2025-07-12 13:58:19
合計ジャッジ時間 4,757 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

'''
dp[i][j][k]:=
i桁目まで見て、
2の倍数がj (0..2)
5の倍数がk (0..2)の個数
'''
MOD = 10 ** 9 + 7
N = input()
LN = len(N)
dp = [[[0] * 3 for _ in range(3)] for _ in range(LN)]
dp[0][0][0] = 1
sum0 = 0
for i in range(LN - 1):
    for j in range(1, 10):
        jn = [0,0]
        if j % 4 == 0:
            jn = [2, 0]
        elif j % 2 == 0:
            jn = [1, 0]
        elif j % 5 == 0:
            jn = [0, 1]
        for k in range(3):
            for l in range(3):
                k2 = min(2, k + jn[0])
                l2 = min(2, l + jn[1])
                dp[i + 1][k2][l2] += dp[i][k][l]
                dp[i + 1][k2][l2] %= MOD
    sum0 += dp[i + 1][2][2]
    sum0 %= MOD

acn = [0, 0]
for i, n in enumerate(N):
    n = int(n)
    ni = LN - i - 1
    Y = [[0] * 3 for _ in range(3)]
    for j in range(3):
        for k in range(3):
            j2 = min(2, j + acn[0])
            k2 = min(2, k + acn[1])
            Y[j2][k2] += dp[ni][j][k]
            Y[j2][k2] %= MOD

    Z = [[0] * 3 for _ in range(3)]
    dummy = 0
    if i == LN - 1:
        n = n + 1
    for j in range(1, n):
        jn = [0, 0]
        if j % 4 == 0:
            jn = [2, 0]
        elif j % 2 == 0:
            jn = [1, 0]
        elif j % 5 == 0:
            jn = [0, 1]
        for k in range(3):
            for l in range(3):
                k2 = min(2, k + jn[0])
                l2 = min(2, l + jn[1])
                Z[k2][l2] += Y[k][l]
                Z[k2][l2] %= MOD
    sum0 += Z[2][2]
    sum0 %= MOD
    if n % 4 == 0:
        acn[0] = min(2, acn[0] + 2)
    elif n % 2 == 0:
        acn[0] = min(2, acn[0] + 1)
    elif n % 5 == 0:
        acn[1] = min(2, acn[1] + 1)


print(sum0)
0