結果

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

ソースコード

diff #
raw source code 

mod = 7000000001

p = [pow(10, i, mod) for i in range(40)]

def calc(x):
    # print(x)
    if x <= 0:
        return 0
        
    s = str(x)
    n = len(s)
    
    ans = 0
    for l in range(1, n):
        ans += 45 * p[l - 1] % mod
        if l > 1:
            ans += 45 * p[l-2] % mod * (p[l] - 10) % mod
    
    dpc = [0, 0]
    dps = [0, 0]
    
    for i in range(n):
        ndpc = [0, 0]
        ndps = [0, 0]
        lim = int(s[i])
        if i == 0:
            ndpc[1] = (lim - 1)
            ndps[1] = (lim * (lim - 1) // 2)
            ndpc[0] = 1
            ndps[0] = lim
        else:
            ndpc[1] += dpc[1] * 10 % mod
            ndps[1] += dps[1] * 10 + 45 * p[i] % mod * dpc[1] % mod
            # d < lim
            ndpc[1] += dpc[0] * lim % mod
            
            v = lim * (lim - 1) // 2
            ndps[1] += dps[0] * lim + v * p[i] * dpc[0] % mod
            ndpc[0] += dpc[0] % mod
            ndps[0] += dps[0] + lim * p[i] % mod * dpc[0] % mod
    
        dpc = [x%mod for x in ndpc]
        dps = [x%mod for x in ndps]
    return ans + sum(dps)

import sys

input = sys.stdin.readline
# import codecs
n = int(input().replace('\u202e', ''))
for i in range(n):
    l, r = [int(x.replace('\u202e', '')) for x in input().split()]
    x = calc(r) - calc(l - 1)
    # print(l, r)
    x = x % mod
    print(str(x))
0