結果

問題 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
52,096 KB
testcase_01 AC 37 ms
52,736 KB
testcase_02 AC 40 ms
51,968 KB
testcase_03 AC 2,309 ms
362,276 KB
testcase_04 AC 2,230 ms
362,604 KB
testcase_05 AC 2,227 ms
362,332 KB
testcase_06 AC 2,244 ms
362,784 KB
testcase_07 AC 2,252 ms
362,324 KB
testcase_08 AC 2,256 ms
362,488 KB
testcase_09 AC 2,238 ms
362,840 KB
testcase_10 AC 2,196 ms
362,536 KB
testcase_11 AC 2,247 ms
362,540 KB
testcase_12 AC 2,487 ms
362,528 KB
testcase_13 AC 2,211 ms
362,476 KB
testcase_14 AC 2,236 ms
362,740 KB
testcase_15 AC 2,236 ms
362,792 KB
testcase_16 AC 2,219 ms
362,736 KB
testcase_17 AC 2,698 ms
362,680 KB
testcase_18 AC 1,846 ms
362,104 KB
testcase_19 AC 2,809 ms
361,968 KB
権限があれば一括ダウンロードができます

ソースコード

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