結果

問題 No.3277 Forever Monotonic Number
コンテスト
ユーザー detteiuu
提出日時 2025-09-19 22:05:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,707 ms / 4,000 ms
コード長 1,258 bytes
コンパイル時間 352 ms
コンパイル使用メモリ 82,564 KB
実行使用メモリ 119,436 KB
最終ジャッジ日時 2025-09-19 22:06:10
合計ジャッジ時間 40,252 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

from bisect import bisect_left, bisect_right

def is_monotonic(n):
    while 10 <= n and sum(int(str(n)[i]) <= int(str(n)[i+1]) for i in range(len(str(n))-1)) == len(str(n))-1:
        n = sum(int(a) for a in str(n))
    return n < 10

def func(n, pre, m):
    if n and is_monotonic(m):
        monotonic.append(m)
    if n == 15:
        return
    for i in range(pre, 10):
        func(n+1, i, m*10+i)

MOD = 998244353

monotonic = []
func(0, 1, 0)
monotonic.sort()

POW1 = [1, 11]
POW0 = [1, 10]
for _ in range(60):
    POW0.append(POW0[-1]**2%MOD)
    POW1.append((POW1[-1]*POW0[-1]%MOD+POW1[-1])%MOD)

for _ in range(int(input())):
    N = int(input())

    diff = monotonic[bisect_left(monotonic, N+1)]-(N+1)

    ans = 0
    for i in range(60):
        if 1<<i & (N+1):
            ans *= POW0[i+1]
            ans %= MOD
            ans += POW1[i]
            ans %= MOD
    
    d, m = divmod(diff, 8)
    SUM = 0
    for i in range(60):
        if 1<<i & d:
            SUM *= POW0[i+1]
            SUM %= MOD
            SUM += POW1[i]
            SUM %= MOD
    ans += SUM*8
    ans %= MOD
    SUM = 1
    for i in range(60):
        if 1<<i & d:
            SUM *= POW0[i+1]
            SUM %= MOD
    ans += SUM*m
    ans %= MOD

    print(ans)
0