結果

問題 No.260 世界のなんとか3
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:26:25
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,749 bytes
コンパイル時間 203 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 78,416 KB
最終ジャッジ日時 2025-06-12 18:27:00
合計ジャッジ時間 10,047 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 MLE * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def subtract_one(s):
    s_list = list(s)
    i = len(s_list) - 1
    while i >= 0 and s_list[i] == '0':
        s_list[i] = '9'
        i -= 1
    if i == -1:
        return '0'
    s_list[i] = str(int(s_list[i]) - 1)
    if s_list[0] == '0' and len(s_list) > 1:
        return ''.join(s_list[1:])
    return ''.join(s_list)

def count_aho(num_str):
    digits = list(map(int, num_str))
    n = len(digits)
    dp_prev = [[[0] * 2 for _ in range(3)] for __ in range(2)]
    dp_prev[1][0][0] = 1  # tight=1, mod3=0, has3=0

    for pos in range(n):
        dp_next = [[[0] * 2 for _ in range(3)] for __ in range(2)]
        for tight in [0, 1]:
            for mod3 in [0, 1, 2]:
                for has3 in [0, 1]:
                    count = dp_prev[tight][mod3][has3]
                    if count == 0:
                        continue
                    max_d = digits[pos] if tight else 9
                    for d in range(0, max_d + 1):
                        new_tight = 1 if (tight and d == max_d) else 0
                        new_mod3_val = (mod3 + d) % 3
                        new_has3_val = 1 if (has3 or d == 3) else 0
                        dp_next[new_tight][new_mod3_val][new_has3_val] = (
                            dp_next[new_tight][new_mod3_val][new_has3_val] + count
                        ) % MOD
        dp_prev = dp_next

    total = 0
    for tight in [0, 1]:
        for mod3 in [0, 1, 2]:
            for has3 in [0, 1]:
                if mod3 == 0 or has3 == 1:
                    total = (total + dp_prev[tight][mod3][has3]) % MOD
    return total

def count_aho_and_eight(num_str):
    digits = list(map(int, num_str))
    n = len(digits)
    dp_prev = [[[[0] * 8 for _ in range(2)] for __ in range(3)] for ___ in range(2)]
    dp_prev[1][0][0][0] = 1  # tight=1, mod3=0, has3=0, mod8=0

    for pos in range(n):
        dp_next = [[[[0] * 8 for _ in range(2)] for __ in range(3)] for ___ in range(2)]
        for tight in [0, 1]:
            for mod3 in [0, 1, 2]:
                for has3 in [0, 1]:
                    for mod8 in range(8):
                        count = dp_prev[tight][mod3][has3][mod8]
                        if count == 0:
                            continue
                        max_d = digits[pos] if tight else 9
                        for d in range(0, max_d + 1):
                            new_tight = 1 if (tight and d == max_d) else 0
                            new_mod3_val = (mod3 + d) % 3
                            new_has3_val = 1 if (has3 or d == 3) else 0
                            new_mod8_val = (mod8 * 10 + d) % 8
                            dp_next[new_tight][new_mod3_val][new_has3_val][new_mod8_val] = (
                                dp_next[new_tight][new_mod3_val][new_has3_val][new_mod8_val] + count
                            ) % MOD
        dp_prev = dp_next

    total = 0
    for tight in [0, 1]:
        for mod3 in [0, 1, 2]:
            for has3 in [0, 1]:
                for mod8 in [0]:
                    if mod3 == 0 or has3 == 1:
                        total = (total + dp_prev[tight][mod3][has3][mod8]) % MOD
    return total

def main():
    A, B = input().split()
    A_minus_1 = subtract_one(A)

    # Calculate count_aho for B and A-1
    count_B_aho = count_aho(B)
    count_Aminus1_aho = count_aho(A_minus_1)
    total_aho = (count_B_aho - count_Aminus1_aho) % MOD

    # Calculate count_aho_and_eight for B and A-1
    count_B_ae = count_aho_and_eight(B)
    count_Aminus1_ae = count_aho_and_eight(A_minus_1)
    total_ae = (count_B_ae - count_Aminus1_ae) % MOD

    # The answer is (total_aho - total_ae) mod MOD
    ans = (total_aho - total_ae) % MOD
    print(ans)

if __name__ == "__main__":
    main()
0