結果

問題 No.8133 ‮Reversed‪
コンテスト
ユーザー tobisatis
提出日時 2026-04-01 22:55:19
言語 C#
(.NET 10.0.201)
コンパイル:
dotnet_c
実行:
/usr/bin/dotnet_wrap
結果
TLE  
実行時間 -
コード長 2,078 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,941 ms
コンパイル使用メモリ 172,544 KB
実行使用メモリ 827,056 KB
最終ジャッジ日時 2026-04-01 22:56:15
合計ジャッジ時間 23,138 ms
ジャッジサーバーID
（参考情報） 		judge4_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other TLE * 5 MLE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (93 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

diff #
raw source code 

#nullable enable

#region
var (_input, _iter) = (Array.Empty<string>(), 0);
T I<T>() where T : IParsable<T>
{
    while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Trim().Split(' '), 0);
    return T.Parse(_input[_iter++], null);
}
#endregion

const long Mod = 1000000007;
var ns = I<string>();
// var n = int.Parse(new string([..ns.Reverse()]));
var n = int.Parse(ns);

var f = new Dictionary<(long, long, bool), (Int128, Int128)>();
(Int128, Int128) F(long x, long j, bool z)
{
    if (j <= 1 && x < 10) return (x * (x + 1) / 2, x + 1);
    var key = (x, j, z);
    if (f.TryGetValue(key, out var cv)) return cv;
    Int128 v = 0;
    Int128 c = 0;
    var d = x / j;
    if (d > 0)
    {
        var (nv, nc) = F(j - 1, j / 10, z);
        if (z) v += nv * 10;
        else v += nv;
        c += nc;
    }
    for (var i = 1; i < d; i++)
    {
        var (nv, nc) = F(j - 1, j / 10, true);
        v += nv * 10 + nc * i;
        c += nc;
    }
    {
        var nz = z || d > 0;
        var (nv, nc) = F(x - j * d, j / 10, nz);
        if (nz) v += nv * 10 + nc * d;
        else v += nv;
        c += nc;
    }
    return f[key] = (v % Mod, c % Mod);
}

long T(long x)
{
    var res = 1L;
    while (x >= 10) (x, res) = (x / 10, res * 10);
    return res;
}

var ans = new List<long>();
for (var i = 0; i < n; i++)
{
    var ls = I<string>();
    var rs = I<string>();
    // var l = long.Parse(new string([..ls.Reverse()]));
    // var r = long.Parse(new string([..rs.Reverse()]));
    var l = long.Parse(ls);
    var r = long.Parse(rs);
    var t = T(r);
    var rns = F(r, t, false).Item1;
    var lns = F(l - 1, t, false).Item1;
    var qns = (rns - lns + Mod) % Mod;
    // var sns = new string([..qns.ToString().Reverse()]);
    var sns = qns.ToString();
    ans.Add(long.Parse(sns));
    // var dbg = 0L;
    // for (var j = 0; j <= r; j++)
    // {
    //     var rev = j.ToString().Reverse();
    //     dbg += long.Parse(new string([..rev]));
    // }
    // Console.WriteLine(dbg);
}
Console.WriteLine(string.Join(Environment.NewLine, ans));
0