結果

問題 No.8133 ‮Reversed‪
コンテスト
ユーザー lif4635
提出日時 2026-04-01 21:56:48
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 1,264 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 128 ms
コンパイル使用メモリ 85,116 KB
実行使用メモリ 168,708 KB
最終ジャッジ日時 2026-04-01 21:57:01
合計ジャッジ時間 11,989 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

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:
            for d in range(1, lim + 1):
                sm = (d < lim)
                ndpc[sm] += 1
                ndps[sm] += d
        else:
            for sm in range(2):
                if dpc[sm] == 0:
                    continue
                limd = 9 if sm else lim
                for d in range(limd + 1):
                    nsm = sm | (d < limd)
                    ndpc[nsm] += dpc[sm] % mod
                    ndps[nsm] += dps[sm] + d * p[i] % mod * dpc[sm] % mod
        
        dpc = ndpc
        dps = ndps
    
    return ans + sum(dps)

# 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