結果

問題 No.3277 Forever Monotonic Number
コンテスト
ユーザー titia
提出日時 2025-09-23 03:50:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,681 ms / 4,000 ms
コード長 1,775 bytes
コンパイル時間 411 ms
コンパイル使用メモリ 82,028 KB
実行使用メモリ 85,788 KB
最終ジャッジ日時 2025-09-23 03:50:23
合計ジャッジ時間 10,341 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

mod=998244353

def calc(x):
    S=str(x)

    SUM=0

    now=0
    for s in S:
        SUM+=int(s)
        if int(s)>=now:
            pass
        else:
            return False
        now=int(s)

    if len(S)==1:
        return True
    else:
        if calc(SUM)==True:
            return True
        else:
            return False

def monotonic(x):
    S=str(x)
    now=0

    for s in S:
        if int(s)>=now:
            pass
        else:
            return False
        now=int(s)

    return True
        
def nextmonotonic(x):
    if monotonic(x)==True:
        return x

    S=str(x)

    L=list(map(int,list(S)))
    XL=L[:]

    flag=0

    for i in range(1,len(L)):
        if flag==1:
            L[i]=L[i-1]
        else:
            if L[i]<L[i-1]:
                flag=1
                L[i]=L[i-1]

    if XL==L:
        for i in range(len(L)-1,-1,-1):
            if L[i]!=9:
                L[i]+=1

    ret="".join(map(str,L))

    return int(ret)

    
    

    

T=int(input())

for tests in range(T):
    n=int(input())

    if calc(n+1)==True:
        ANS=(pow(10,n+1,mod)-1)*pow(9,mod-2,mod)%mod

        print(ANS)
        continue

    now=n+2

    while True:
        #print(now)
        if monotonic(now)==True:
            if calc(now)==True:
                ANS=(pow(10,n+1,mod)-1)*pow(9,mod-2,mod)%mod
                k=now-n-1

                q=k//8
                rest=k%8
                keta=1

                ANS+=8*(pow(10,q,mod)-1)*pow(9,mod-2,mod)%mod
                ANS+=pow(10,q,mod)*rest

                print(ANS%mod)   
                break

        now2=nextmonotonic(now)

        if now==now2:
            now=nextmonotonic(now+1)
        else:
            now=now2
0