結果

問題 No.8133 ‮Reversed‪
コンテスト
ユーザー tobisatis
提出日時 2026-04-01 23:15:15
言語 C#
(.NET 10.0.201)
コンパイル:
dotnet_c
実行:
/usr/bin/dotnet_wrap
結果
AC  
実行時間 1,740 ms / 2,000 ms
コード長 2,329 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 7,129 ms
コンパイル使用メモリ 174,300 KB
実行使用メモリ 253,036 KB
最終ジャッジ日時 2026-04-01 23:15:41
合計ジャッジ時間 23,310 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 6
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (85 ミリ秒)。
  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 = 7000000001;
var ns = I<string>();
// var n = int.Parse(new string([..ns.Reverse()]));
var n = int.Parse(ns);

var tens = new long[20];
tens[0] = 1;
for (var i = 1; i < 20; i++) tens[i] = tens[i - 1] * 10;

var f = new Dictionary<long, (long, long)>[20, 2];
(long, long) F(long x, int j, bool z)
{
    if (j == 0 && x < 10) return (x * (x + 1) / 2, x + 1);
    var zn = z ? 1 : 0;
    if (f[j, zn].TryGetValue(x, out var cv)) return cv;
    long v = 0;
    long c = 0;
    var ten = tens[j];
    var d = x / ten;
    if (d > 0)
    {
        var (nv, nc) = F(ten - 1, j - 1, z);
        if (z) v += nv * 10;
        else v += nv;
        c += nc;
    }
    if (d > 1)
    {
        var (nv, nc) = F(ten - 1, j - 1, true);
        v += nv * 10 * (d - 1) + nc * d * (d - 1) / 2;
        c += nc * (d - 1);
    }
    {
        var nz = z || d > 0;
        var (nv, nc) = F(x - ten * d, j - 1, nz);
        if (nz) v += nv * 10 + nc * d;
        else v += nv;
        c += nc;
    }
    var res = (v % Mod, c % Mod);
    f[j, zn][x] = res;
    return res;
}

int T(long x)
{
    var res = 0;
    while (x >= 10) (x, res) = (x / 10, res + 1);
    return res;
}

var ans = new List<long>();
for (var lp = 0; lp < n; lp++)
{
    for (var i = 0; i < 20; i++)
    {
        f[i, 0] = new();
        f[i, 1] = new();
    }
    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