結果

問題 No.3277 Forever Monotonic Number
コンテスト
ユーザー miya145592
提出日時 2025-09-20 15:37:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,084 ms / 4,000 ms
コード長 1,321 bytes
コンパイル時間 325 ms
コンパイル使用メモリ 82,820 KB
実行使用メモリ 205,884 KB
最終ジャッジ日時 2025-09-20 15:37:59
合計ジャッジ時間 10,115 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

def check(i, n):
    if dp[i]<n+1:
        return False
    return True

def calc(s, n):
    #print(s, n)
    if s>(n+1)*9:
        nine = s//9
        amari = s%9
        one = 0
    else:
        t = s-(n+1)
        nine = t//8
        amari = t%8
        amari += 1
        one = (n+1)-(nine+1)
    ret = 0
    ret += (pow(10, nine, MOD) - 1) % MOD
    ret += pow(10, nine, MOD) * amari % MOD
    ret += (pow(10, one, MOD) - 1) % MOD * inv_9 % MOD * pow(10, nine+1, MOD) % MOD
    ret %= MOD
    return ret

def wa(x):
    ret = 0
    while x>0:
        ret += x%10
        x//=10
    return ret

import sys
input = sys.stdin.readline
MOD = 998244353
T = int(input())
N = [int(input()) for _ in range(T)]
inv_9 = pow(9, MOD-2, MOD)
mono = [set() for _ in range(15)]
mono[0] = set([i for i in range(1, 10)])
for i in range(14):
    for j in mono[i]:
        tmp = j%10
        for k in range(tmp, 10):
            tmp2 = j*10+k
            mono[i+1].add(tmp2)
dp = set()
for i in range(15):
    for j in mono[i]:
        tmp = wa(j)
        if tmp<10 or tmp in dp:
            dp.add(j)
dp = list(dp)
dp.sort()
for n in N:
    l = -1
    r = len(dp)
    while r-l>1:
        mid = (l+r)//2
        if check(mid, n):
            r = mid
        else:
            l = mid
    S = dp[r]
    ans = calc(S, n)
    print(ans)
0