結果

問題 No.8133 ‮Reversed‪
コンテスト
ユーザー 👑 Nachia
提出日時 2026-04-01 23:33:45
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,579 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 831 ms
コンパイル使用メモリ 96,084 KB
実行使用メモリ 103,924 KB
最終ジャッジ日時 2026-04-01 23:33:59
合計ジャッジ時間 10,943 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge4_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }

using i128 = __int128_t;

ll M = 7000000001;

i128 rev(i128 x){
    ll h = 0;
    while(x){
        h = h * 10 + x % 10;
        x /= 10;
    }
    return h;
}
i128 g(i128 x){
    i128 ans = 0;
    REP(i,x) ans += rev(i);
    return ans % M;
}
i128 p10[20];
i128 offset = g(10);
i128 f(ll x){
    if(x <= 15) return g(x);
    i128 ans = offset;
    ll maxdig = to_string(x).size();
    for(ll d=2; d<maxdig; d++){
        ans += p10[d-1] / 9 * 45 % M * p10[d-1] % M * 9;
        ans += 45 * (p10[d-1] % M) % M;
    }
    ll ti = 1, h = p10[maxdig];
    while(x > 0){
        maxdig--;
        while(x % 10) ans += rev(--x) * ti % M;
        h /= 10;
        x /= 10;
        if (x == 0) break;
        ans += i128(h) % M * 45 % M * (x-(h/10)) % M * ti % M;
        ti = ti * 10 % M;
    }
    return ans % M;
}

void testcase(){
    ll l, r; cin >> l >> r; r++;
    auto fl = f(l);
    auto fr = f(r);
    if(fl > fr) fr += M;
    cout << ll(fr - fl) << "\n";
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  p10[0] = 1; REP(i,19) p10[i+1] = p10[i] * 10;
  ll T; cin >> T; REP(t,T)
  testcase();
  return 0;
}
0