結果

問題 No.3277 Forever Monotonic Number
コンテスト
ユーザー lif4635
提出日時 2025-09-19 20:17:09
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,165 ms / 4,000 ms
コード長 725 bytes
コンパイル時間 371 ms
コンパイル使用メモリ 82,724 KB
実行使用メモリ 111,228 KB
最終ジャッジ日時 2025-09-19 20:17:33
合計ジャッジ時間 22,649 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import *
from bisect import *
mod = 998244353

def c(x):
    x = str(x)
    l = len(x)
    if l == 1: return True
    for i in range(l-1):
        if x[i] > x[i+1]: return False
    return c(sum(map(int, x)))

ok = []
for p in combinations_with_replacement(range(16), 9):
    p += (16,)
    x, t = 0, 0
    for i in range(16):
        x = x * 10 + t
        while p[t] == i: t += 1
    if c(x): ok.append(x)
ok.sort()

inv9 = pow(9, -1, mod)
for i in range(int(input())):
    n = int(input()) + 1
    s = ok[bisect_left(ok, n)]
    p, q = divmod(s - n, 8)
    ans = (pow(10, n, mod) - 1) * inv9 % mod
    ans += (pow(10, p, mod) - 1) * 8 * inv9 % mod
    ans += pow(10, p, mod) * q % mod
    print(ans % mod)
0