結果
問題 |
No.3277 Forever Monotonic Number
|
ユーザー |
👑 |
提出日時 | 2025-09-04 23:41:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,485 ms / 4,000 ms |
コード長 | 947 bytes |
コンパイル時間 | 431 ms |
コンパイル使用メモリ | 82,512 KB |
実行使用メモリ | 245,668 KB |
最終ジャッジ日時 | 2025-09-05 00:37:26 |
合計ジャッジ時間 | 25,160 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 9 |
ソースコード
from bisect import bisect_left from itertools import combinations LIMIT = 15 def enum(): for comb in combinations(range(LIMIT + 9), r=9): comb = list(comb) val = 0 for i, c in enumerate(comb): val += (10 ** (c - i) - 1) // 9 yield val cand = set() for v in sorted(enum()): digit_sum = sum(int(x) for x in str(v)) if digit_sum <= 9 or digit_sum in cand: cand.add(v) cand = sorted(cand) MOD = 998244353 def solve(): N = int(input()) min_digit_sum = cand[bisect_left(cand, N + 1)] ans = (pow(10, N + 1, MOD) - 1) * pow(9, -1, MOD) % MOD remain = min_digit_sum - (N + 1) d, r = remain // 8, remain % 8 ans += (pow(10, d + 1, MOD) - 1) * pow(9, -1, MOD) * r % MOD ans += (pow(10, d, MOD) - 1) * pow(9, -1, MOD) * (8 - r) % MOD ans %= MOD print(ans) if __name__ == "__main__": T = int(input()) for _ in range(T): solve()