結果

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

ソースコード

diff # 

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static int NN => int.Parse(ReadLine());
    static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
    static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();
    static int[] NMi => ReadLine().Split().Select(c => int.Parse(c) - 1).ToArray();
    static int[][] NMap(int n) => Enumerable.Repeat(0, n).Select(_ => NMi).ToArray();

    public static void Main()
    {
        Init();
        Solve();
    }
    static void Init()
    {
        var f = new HashSet<long>();
        for (var i = 1; i <= 9; ++i) f.Add(i);
        for (var i = 10; i < 1000; ++i)
        {
            var prev = 10;
            var tmp = i;
            var sum = 0;
            var flg = true;
            while (tmp > 0)
            {
                var cur = tmp % 10;
                if (cur > prev)
                {
                    flg = false;
                    break;
                }
                sum += cur;
                tmp /= 10;
                prev = cur;
            }
            if (flg && f.Contains(sum)) f.Add(i);
        }
        flist = new List<long>(f);
        flist.Sort();
    }
    static void Solve()
    {
        var t = NN;
        var ans = new long[t];
        for (var u = 0; u < t; ++u)
        {
            var n = long.Parse(ReadLine());
            ans[u] = Forever(n);
        }
        WriteLine(string.Join("\n", ans));
    }
    static int mod = 998_244_353;
    static int rev9 = 443_664_157;
    static List<long> flist = new List<long>();
    static long Forever(long n)
    {
        checked
        {
            var len = n + 1;
            var fm = NextFm(len);
            var eightcount = (fm - len) / 8;
            var rest = (fm - len) % 8;
            var e10 = Exp(10, eightcount);
            return ((Exp(10, len) - 1 + mod) % mod * rev9 % mod + rest * e10 % mod + (e10 - 1 + mod) % mod * 8 % mod * rev9 % mod) % mod;
        }
    }
    static long NextFm(long n)
    {
        if (n < 1000)
        {
            return flist[LowerBound(0, n, flist)];
        }
        var s = n.ToString();
        var t = new char[s.Length];
        t[0] = s[0];
        var over = false;
        for (var i = 1; i < s.Length; ++i)
        {
            if (over)
            {
                t[i] = t[i - 1];
            }
            else if (s[i - 1] > s[i])
            {
                over = true;
                t[i] = s[i - 1];
            }
            else t[i] = s[i];
        }
        var ans = GetT(t);
        for (var i = t.Length - 1; i >= 0; --i)
        {
            if (t[i] < '9')
            {
                ++t[i];
                for (var j = i + 1; j < t.Length; ++j) t[j] = t[i];
                ans = Math.Min(ans, GetT(t));
            }
        }
        var u = new char[s.Length + 1];
        for (var i = 0; i < u.Length; ++i) u[i] = '1';
        ans = Math.Min(ans, GetT(u));
        return ans;
    }
    static long GetT(char[] _t)
    {
        var t = (char[])_t.Clone();
        var sum = 0;
        foreach (var ti in t) sum += ti - '0';
        var nsum = flist[LowerBound(0, sum, flist)];
        var rest = nsum - sum;
        for (var i = t.Length - 1; i >= 0; --i)
        {
            if (rest == 0) break;
            while (t[i] < '9')
            {
                if (rest == 0) break;
                ++t[i];
                --rest;
            }
        }
        if (rest > 0)
        {
            return long.MaxValue;
        }
        return long.Parse(string.Concat(t));
    }
    static int LowerBound(int left, long min, IList<long> list)
    {
        if (list[left] >= min) return left;
        var ng = left;
        var ok = list.Count;
        while (ok - ng > 1)
        {
            var center = (ng + ok) / 2;
            if (list[center] < min) ng = center;
            else ok = center;
        }
        return ok;
    }
    static long Exp(long n, long p)
    {
        long _n = n % mod;
        var _p = p;
        var result = 1L;
        if ((_p & 1) == 1) result *= _n;
        while (_p > 0)
        {
            _n = _n * _n % mod;
            _p >>= 1;
            if ((_p & 1) == 1) result = result * _n % mod;
        }
        return result;
    }
}
0