結果

問題 No.3277 Forever Monotonic Number
ユーザー tobisatis
提出日時 2025-09-19 23:01:51
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 1,744 ms / 4,000 ms
コード長 1,951 bytes
コンパイル時間 9,268 ms
コンパイル使用メモリ 169,692 KB
実行使用メモリ 220,276 KB
最終ジャッジ日時 2025-09-19 23:02:22
合計ジャッジ時間 18,380 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (133 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

#nullable enable

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

const int Mod = 998244353;
static long Power(long v, long p)
{
    var (res, k) = (1L, v);
    while (p > 0)
    {
        if ((p & 1) > 0) res = res * k % Mod;
        k = k * k % Mod;
        p >>= 1;
    }
    return res;
}

static long NextMonotone(long n)
{
    var s = n.ToString().Select(e => e - '0').ToArray();
    for (var i = 1; i < s.Length; i++)
    {
        if (s[i - 1] > s[i])
        {
            for (var j = i; j < s.Length; j++) s[j] = s[i - 1];
            break;
        }
    }
    var res = 0L;
    for (var i = 0; i < s.Length; i++) res = res * 10 + s[i];
    return res;
}

static (long, bool) Op(long n)
{
    var res = 0L;
    var last = 10L;
    var monotone = true;
    while (n > 0)
    {
        var (div, rem) = long.DivRem(n, 10);
        res += rem;
        n = div;
        monotone &= rem <= last;
        last = rem;
    }
    return (res, monotone);
}

static bool J(long n)
{
    if (n < 10) return true;
    var (next, monotone) = Op(n);
    if (!monotone) return false;
    return J(next);
}

long Solve(long n)
{
    if (n == 0) return 1;
    var m = n + 1;
    while (true)
    {
        if (J(m)) break;
        m = NextMonotone(m + 1);
    }
    var d = m - n - 1;
    var p = d / 8;
    var q = d % 8;
    var elz = Power(10, n + 1 - p - 1) + Mod - 1;
    elz = elz * Power(9, Mod - 2) % Mod;
    elz = elz * Power(10, p + 1) % Mod;
    var p10 = Power(10, p);
    var tns = (p10 + Mod - 1 + p10 * (q + 1)) % Mod;
    tns = (tns + elz) % Mod;
    return tns;
}

var t = I<int>();
var ans = new long[t];
for (var i = 0; i < t; i++) ans[i] = Solve(I<long>());
Console.WriteLine(string.Join(Environment.NewLine, ans));
0