結果
問題 |
No.3277 Forever Monotonic Number
|
ユーザー |
![]() |
提出日時 | 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