結果

問題 No.3277 Forever Monotonic Number
コンテスト
ユーザー 👑 loop0919
提出日時 2025-09-04 23:41:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,485 ms / 4,000 ms
コード長 947 bytes
コンパイル時間 431 ms
コンパイル使用メモリ 82,512 KB
実行使用メモリ 245,668 KB
最終ジャッジ日時 2025-09-05 00:37:26
合計ジャッジ時間 25,160 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

from bisect import bisect_left
from itertools import combinations

LIMIT = 15


def enum():
    for comb in combinations(range(LIMIT + 9), r=9):
        comb = list(comb)
        val = 0

        for i, c in enumerate(comb):
            val += (10 ** (c - i) - 1) // 9

        yield val


cand = set()

for v in sorted(enum()):
    digit_sum = sum(int(x) for x in str(v))
    if digit_sum <= 9 or digit_sum in cand:
        cand.add(v)

cand = sorted(cand)
MOD = 998244353


def solve():
    N = int(input())
    min_digit_sum = cand[bisect_left(cand, N + 1)]

    ans = (pow(10, N + 1, MOD) - 1) * pow(9, -1, MOD) % MOD
    remain = min_digit_sum - (N + 1)

    d, r = remain // 8, remain % 8
    ans += (pow(10, d + 1, MOD) - 1) * pow(9, -1, MOD) * r % MOD
    ans += (pow(10, d, MOD) - 1) * pow(9, -1, MOD) * (8 - r) % MOD
    ans %= MOD

    print(ans)


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