結果

問題 No.2867 NOT FOUND 404 Again
コンテスト
ユーザー るこーそー
提出日時 2024-09-28 10:27:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,809 ms / 3,000 ms
コード長 635 bytes
コンパイル時間 200 ms
コンパイル使用メモリ 82,096 KB
実行使用メモリ 362,840 KB
最終ジャッジ日時 2024-09-28 10:28:32
合計ジャッジ時間 40,237 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD=998244353

n=input()

#dp[i][j][k] 
#i桁目まで見たときに、j=0:未満フラグが立っていない j=1:立っている 404のk番目までを満たす
dp=[[[0]*4 for _ in range(2)] for _ in range(len(n)+1)]
dp[0][0][0]=1
for i in range(len(n)):
    ch=int(n[i])
    for j in range(2):
        for k in range(3):
            for d in range(10 if j else ch+1):
                cond=(k==0 and d==4) or (k==1 and d==0) or (k==2 and d==4)
                dp[i+1][j|(d<ch)][k+1 if cond else d==4]+=dp[i][j][k]
                dp[i+1][j|(d<ch)][k+1 if cond else d==4]%=MOD

print(((sum(dp[-1][0][:3])+sum(dp[-1][1][:3]))-1)%MOD)
0