結果

問題 No.2867 NOT FOUND 404 Again
コンテスト
ユーザー flippergo
提出日時 2025-03-07 21:00:57
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,530 bytes
コンパイル時間 417 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 915,104 KB
最終ジャッジ日時 2025-03-07 21:01:06
合計ジャッジ時間 8,238 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 MLE * 1
other WA * 1 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353
A = list(input().strip())
N = len(A)
A = ["0"]+A
if N<3:
    print("".join(A))
else:
    A = [int(A[i]) for i in range(N+1)]
    dp = [[[[0 for _ in range(2)] for _ in range(10)] for _ in range(10)] for _ in range(N+1)]
    dp[2][A[2]][A[1]][0] = 1
    for j1 in range(A[2]):
        dp[2][j1][A[1]][1] = 1
    for j1 in range(10):
        for j2 in range(A[1]):
            dp[2][j1][j2][1] = 1
    for i in range(2,N):
        for j1 in range(10):
            for j2 in range(10):
                if j1!=0 or j2!=4:
                    for k1 in range(10):
                        dp[i+1][k1][j1][1] = (dp[i+1][k1][j1][1]+dp[i][j1][j2][1])%MOD
                    dp[i+1][A[i+1]][j1][0] = (dp[i+1][A[i+1]][j1][0]+dp[i][j1][j2][0])%MOD
                    for k1 in range(A[i+1]):
                        dp[i+1][k1][j1][1] = (dp[i+1][k1][j1][1]+dp[i][j1][j2][0])%MOD
                else:
                    for k1 in range(10):
                        if k1==4:continue
                        dp[i+1][k1][j1][1] = (dp[i+1][k1][j1][1]+dp[i][j1][j2][1])%MOD
                    if A[i+1]!=4:
                        dp[i+1][A[i+1]][j1][0] = (dp[i+1][A[i+1]][j1][0]+dp[i][j1][j2][0])%MOD
                    for k1 in range(A[i+1]):
                        if k1==4:continue
                        dp[i+1][k1][j1][1] = (dp[i+1][k1][j1][1]+dp[i][j1][j2][0])%MOD
    ans = 0
    for j1 in range(10):
        for j2 in range(10):
            ans = (ans+dp[N][j1][j2][0]+dp[N][j1][j2][1])%MOD
    print((ans-1)%MOD)
0