結果

問題 No.3242 Count 8 Included Numbers (Hard)
コンテスト
ユーザー shimon
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0