結果
問題 |
No.3242 Count 8 Included Numbers (Hard)
|
ユーザー |
|
提出日時 | 2025-09-30 23:32:56 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 861 bytes |
コンパイル時間 | 542 ms |
コンパイル使用メモリ | 82,452 KB |
実行使用メモリ | 302,032 KB |
最終ジャッジ日時 | 2025-09-30 23:33:30 |
合計ジャッジ時間 | 33,052 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 13 TLE * 7 |
ソースコード
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] DP[i + 1][1][k | (add == 8)] %= MOD elif j == 0 and add == int(N[i]): DP[i + 1][0][k | (add == 8)] += DP[i][j][k] DP[i + 1][0][k | (add == 8)] %= MOD elif j == 1: DP[i + 1][1][k | (add == 8)] += DP[i][j][k] DP[i + 1][1][k | (add == 8)] %= MOD print((DP[l][0][1] + DP[l][1][1]) % MOD)