結果

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

ソースコード

diff # 

MOD = 10**9 + 7

def subtract_one(s):
    s_list = list(s)
    i = len(s_list) - 1
    carry = 1
    while i >= 0 and carry:
        digit = ord(s_list[i]) - ord('0')
        if digit >= carry:
            s_list[i] = str(digit - carry)
            carry = 0
        else:
            s_list[i] = str(10 + digit - carry)
            carry = 1
        i -= 1
    result = ''.join(s_list).lstrip('0')
    if not result:
        return '0'
    return result

def count_aho(s):
    n = len(s)
    from collections import defaultdict
    dp = [defaultdict(lambda: defaultdict(lambda: defaultdict(int))) for _ in range(n+1)]
    dp[0][0][0][1] = 1  # sum_mod3, has_3, tight

    for pos in range(n):
        current = dp[pos]
        next_dp = defaultdict(lambda: defaultdict(lambda: defaultdict(int)))
        for sum_mod in current:
            for has_3 in current[sum_mod]:
                for tight in current[sum_mod][has_3]:
                    cnt = current[sum_mod][has_3][tight]
                    if cnt == 0:
                        continue
                    max_d = int(s[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_sum = (sum_mod + d) % 3
                        new_has_3 = 1 if (has_3 or d == 3) else 0
                        next_dp[new_sum][new_has_3][new_tight] = (next_dp[new_sum][new_has_3][new_tight] + cnt) % MOD
        dp[pos+1] = next_dp

    total = 0
    for sum_mod in dp[n]:
        for has_3 in dp[n][sum_mod]:
            for tight in dp[n][sum_mod][has_3]:
                if sum_mod == 0 or has_3:
                    total = (total + dp[n][sum_mod][has_3][tight]) % MOD
    return total

def count_aho_seisyun(s):
    n = len(s)
    from collections import defaultdict
    dp = [defaultdict(lambda: defaultdict(lambda: defaultdict(lambda: defaultdict(int)))) for _ in range(n+1)]
    dp[0][0][0][0][1] = 1  # sum_mod3, mod8, has_3, tight

    for pos in range(n):
        current = dp[pos]
        next_dp = defaultdict(lambda: defaultdict(lambda: defaultdict(lambda: defaultdict(int))))
        for sum_mod in current:
            for mod8 in current[sum_mod]:
                for has_3 in current[sum_mod][mod8]:
                    for tight in current[sum_mod][mod8][has_3]:
                        cnt = current[sum_mod][mod8][has_3][tight]
                        if cnt == 0:
                            continue
                        max_d = int(s[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_sum = (sum_mod + d) % 3
                            new_mod8 = (mod8 * 10 + d) % 8
                            new_has_3 = 1 if (has_3 or d == 3) else 0
                            next_dp[new_sum][new_mod8][new_has_3][new_tight] = (next_dp[new_sum][new_mod8][new_has_3][new_tight] + cnt) % MOD
        dp[pos+1] = next_dp

    total = 0
    for sum_mod in dp[n]:
        for mod8 in dp[n][sum_mod]:
            for has_3 in dp[n][sum_mod][mod8]:
                for tight in dp[n][sum_mod][mod8][has_3]:
                    if mod8 == 0 and (sum_mod == 0 or has_3):
                        total = (total + dp[n][sum_mod][mod8][has_3][tight]) % MOD
    return total

A, B = input().split()

A_minus_1 = subtract_one(A)

aho_B = count_aho(B)
aho_A = count_aho(A_minus_1)
total_aho = (aho_B - aho_A) % MOD

seisyun_B = count_aho_seisyun(B)
seisyun_A = count_aho_seisyun(A_minus_1)
total_seisyun = (seisyun_B - seisyun_A) % MOD

ans = (total_aho - total_seisyun) % MOD
print(ans)
0