結果
| 問題 |
No.3242 Count 8 Included Numbers (Hard)
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2025-09-30 23:30:36 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 732 bytes |
| コンパイル時間 | 385 ms |
| コンパイル使用メモリ | 82,356 KB |
| 実行使用メモリ | 302,000 KB |
| 最終ジャッジ日時 | 2025-09-30 23:31:11 |
| 合計ジャッジ時間 | 34,234 ms |
|
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 8 TLE * 12 |
ソースコード
N = input()
l = len(N)
DP = [[[0] * 2 for _ in range(2)] for _ in range(l + 1)]
# DP[i][j][k]: i桁目まで見たときに、j:Nと一致しているか(0:一致, 1:不一致)、k:8を含むか
DP[0][0][0] = 1
MOD = 998244353
for i in range(l):
for j in range(2):
for k in range(2):
for add in range(10):
if j == 0 and add < int(N[i]):
DP[i + 1][1][k | (add == 8)] += DP[i][j][k]
elif j == 0 and add == int(N[i]):
DP[i + 1][0][k | (add == 8)] += DP[i][j][k]
elif j == 1:
DP[i + 1][1][k | (add == 8)] += DP[i][j][k]
DP[i + 1][j][k] %= MOD
print((DP[l][0][1] + DP[l][1][1]) % MOD)