結果

問題 No.3277 Forever Monotonic Number
コンテスト
ユーザー 👑 loop0919
提出日時 2025-09-08 21:58:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,405 ms / 4,000 ms
コード長 1,885 bytes
コンパイル時間 497 ms
コンパイル使用メモリ 82,256 KB
実行使用メモリ 164,148 KB
最終ジャッジ日時 2025-09-10 01:13:03
合計ジャッジ時間 14,439 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

from bisect import bisect_left


def is_monotonic(n: int) -> bool:
    """整数 n が monotonic か判定する"""
    str_n = str(n)
    for i in range(len(str_n) - 1):
        if int(str_n[i]) > int(str_n[i + 1]):
            return False
    return True


def digit_sum(n: int) -> int:
    """整数 n の桁和"""
    str_n = str(n)
    return sum(int(i) for i in str_n)


def forever_monotonics(L: int) -> list[int]:
    """10**L 未満の forever-monotonic な整数を列挙する"""
    is_fm = [False] * (L * 9 + 1)
    for i in range(L * 9 + 1):
        if i <= 9 or (is_monotonic(i) and is_fm[digit_sum(i)]):
            is_fm[i] = True

    # mono_list[d][i] : 最上位が i となる d 桁の monotonic な整数の配列
    mono_list = [[[] for _ in range(10)] for _ in range(L)]
    mono_list[0] = [[i] for i in range(10)]

    # fm_list : forever-monotonic な整数を昇順に列挙した配列
    fm_list = [i for i in range(1, 10)]

    for d in range(1, L):
        for i in range(1, 10):
            for j in range(i, 10):
                for mono in mono_list[d - 1][j]:
                    next_mono = i * (10**d) + mono
                    mono_list[d][i].append(next_mono)

                    if is_fm[digit_sum(next_mono)]:
                        fm_list.append(next_mono)

    return fm_list


# 10**15 未満の forever-monotonic な整数を列挙
fm_list = forever_monotonics(15)

P = 998244353
inv_9 = pow(9, P - 2, P)


def solve():
    N = int(input())
    digit = fm_list[bisect_left(fm_list, N + 1)]

    div = (digit - (N + 1)) // 8
    rem = (digit - (N + 1)) % 8

    ans = (pow(10, N + 1, P) - 1) * inv_9 % P
    ans += (pow(10, div + 1, P) - 1) * rem * inv_9 % P
    ans += (pow(10, div, P) - 1) * (8 - rem) * inv_9 % P
    ans %= P

    print(ans)


if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        solve()
0