結果

問題 No.8133 ‮Reversed‪
コンテスト
ユーザー KumaTachiRen
提出日時 2026-03-27 01:04:18
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 779 ms / 2,000 ms
コード長 2,636 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 720 ms
コンパイル使用メモリ 85,544 KB
実行使用メモリ 230,232 KB
最終ジャッジ日時 2026-04-01 20:52:45
合計ジャッジ時間 5,319 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# Test: Gemini

import sys

def main():
    # 入力を一括で読み込み高速化
    input_data = sys.stdin.read().split()
    if not input_data:
        return
        
    T = int(input_data[0])
    MOD = 7000000001
    
    # --- 前計算 ---
    # P[i] = 10^0 + 10^1 + ... + 10^{i-1} を前計算
    P = [0] * 20
    for i in range(1, 20):
        P[i] = P[i-1] + 10**(i-1)
        
    # S_FULL[L] : 桁数 L の正整数すべての rev(i) の総和
    S_FULL = [0] * 20
    S_FULL[1] = 45
    for L in range(2, 20):
        sum_10 = P[L] - P[1]
        S_FULL[L] = 45 * (10 ** (L - 1)) + 405 * (10 ** (L - 2)) * sum_10

    # 1 から x までの rev(i) の総和を求める関数
    def calc(x):
        if x <= 0:
            return 0
            
        s = str(x)
        K = len(s)
        
        # 1. 桁数が K 未満のものの総和
        ans = sum(S_FULL[1:K])
        
        prefix_sum = 0
        # 2. 桁数が K で、i 桁目で初めて x の値より小さくなるものの総和
        for i in range(K):
            xi = int(s[i])
            
            # 選べる数字 d の範囲
            start_d = 1 if i == 0 else 0
            end_d = xi - 1
            
            # 下位桁の自由度
            C = 10 ** (K - 1 - i)
            
            # 下位桁の寄与の合計
            suffix_sum = 0
            if K - 1 - i > 0:
                sum_j = P[K] - P[i+1]
                suffix_sum = 45 * (10 ** (K - 2 - i)) * sum_j
                
            if end_d >= start_d:
                count = end_d - start_d + 1
                sum_d = (start_d + end_d) * count // 2
                
                # 決定済みの上位桁の寄与
                ans += prefix_sum * C * count
                # i 桁目自身の寄与
                ans += sum_d * (10 ** i) * C
                # 自由な下位桁の寄与
                ans += suffix_sum * count
                
            # 次の桁の計算に向けて、上位桁の寄与状態を更新
            prefix_sum += xi * (10 ** i)
            
        # 3. x 自身の寄与
        ans += int(s[::-1])
        
        return ans

    # --- 各テストケースの処理 ---
    out = []
    idx = 1
    for _ in range(T):
        if idx >= len(input_data): 
            break
        L = int(input_data[idx])
        R = int(input_data[idx+1])
        idx += 2
        
        # 累積和の要領で区間の和を求める
        res = (calc(R) - calc(L - 1)) % MOD
        out.append(str(res))
        
    sys.stdout.write('\n'.join(out) + '\n')

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