結果

問題 No.260 世界のなんとか3
ユーザー lam6er
提出日時 2025-04-15 21:28:42
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 4,673 bytes
コンパイル時間 150 ms
コンパイル使用メモリ 81,836 KB
実行使用メモリ 201,756 KB
最終ジャッジ日時 2025-04-15 21:31:46
合計ジャッジ時間 3,697 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 MLE * 1
other MLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def decrement(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'  # This case should not occur as per problem constraints
    s_list[i] = str(int(s_list[i]) - 1)
    # Remove leading zero if any
    result = ''.join(s_list)
    if len(result) > 1:
        result = result.lstrip('0')
        if not result:  # All zeros were stripped
            return '0'
    return result

def calculate_aho(digits):
    n = len(digits)
    dp = [{} for _ in range(n+1)]
    dp[0] = { (0, 0, True, True): 1 }
    for pos in range(n):
        current_dp = dp[pos]
        next_dp = {}
        for state, count in current_dp.items():
            mod3, has_three, tight, leading_zero = state
            max_d = digits[pos] if tight else 9
            for d in range(0, max_d + 1):
                new_tight = tight and (d == max_d)
                new_leading_zero = leading_zero and (d == 0)
                if leading_zero:
                    if d == 0:
                        new_mod3 = 0
                        new_has_three = has_three
                    else:
                        new_mod3 = d % 3
                        new_has_three = 1 if d == 3 else 0
                        new_leading_zero = False
                else:
                    new_mod3 = (mod3 * 10 + d) % 3
                    new_has_three = has_three or (d == 3)
                new_has_three_flag = 1 if new_has_three else 0
                new_state = (new_mod3, new_has_three_flag, new_tight, new_leading_zero)
                if new_state in next_dp:
                    next_dp[new_state] = (next_dp[new_state] + count) % MOD
                else:
                    next_dp[new_state] = count % MOD
        dp[pos+1] = next_dp
    total = 0
    for state, count in dp[n].items():
        mod3, has_three, _, leading_zero = state
        if leading_zero:
            total = (total + count) % MOD
        else:
            if mod3 == 0 or has_three:
                total = (total + count) % MOD
    return total

def calculate_aho_and_8(digits):
    n = len(digits)
    dp = [{} for _ in range(n+1)]
    dp[0] = { (0, 0, 0, True, True): 1 }
    for pos in range(n):
        current_dp = dp[pos]
        next_dp = {}
        for state, count in current_dp.items():
            mod8, mod3, has_three, tight, leading_zero = state
            max_d = digits[pos] if tight else 9
            for d in range(0, max_d + 1):
                new_tight = tight and (d == max_d)
                new_leading_zero = leading_zero and (d == 0)
                if leading_zero:
                    if d == 0:
                        new_mod8_val = 0
                        new_mod3_val = 0
                        new_has_three_val = has_three
                    else:
                        new_mod8_val = d % 8
                        new_mod3_val = d % 3
                        new_has_three_val = 1 if d == 3 else 0
                        new_leading_zero = False
                else:
                    new_mod8_val = (mod8 * 10 + d) % 8
                    new_mod3_val = (mod3 * 10 + d) % 3
                    new_has_three_val = has_three or (d == 3)
                new_has_three_flag = 1 if new_has_three_val else 0
                new_state = (new_mod8_val, new_mod3_val, new_has_three_flag, new_tight, new_leading_zero)
                if new_state in next_dp:
                    next_dp[new_state] = (next_dp[new_state] + count) % MOD
                else:
                    next_dp[new_state] = count % MOD
        dp[pos+1] = next_dp
    total = 0
    for state, count in dp[n].items():
        mod8, mod3, has_three, _, leading_zero = state
        if leading_zero:
            total = (total + count) % MOD
        else:
            if mod8 == 0 and (mod3 == 0 or has_three):
                total = (total + count) % MOD
    return total

def main():
    A, B = input().split()
    A_minus_1 = decrement(A)
    # Process B
    digits_B = [int(c) for c in B]
    aho_B = calculate_aho(digits_B)
    aho_and_8_B = calculate_aho_and_8(digits_B)
    res_B = (aho_B - aho_and_8_B) % MOD
    # Process A-1
    if A_minus_1 == '0':
        digits_A_minus_1 = [0]
    else:
        digits_A_minus_1 = [int(c) for c in A_minus_1]
    aho_Aminus1 = calculate_aho(digits_A_minus_1)
    aho_and_8_Aminus1 = calculate_aho_and_8(digits_A_minus_1)
    res_Aminus1 = (aho_Aminus1 - aho_and_8_Aminus1) % MOD
    # Compute the answer
    answer = (res_B - res_Aminus1) % MOD
    if answer < 0:
        answer += MOD
    print(answer)

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