結果
| 問題 | 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 | 
ソースコード
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
    
            
            
            
        