結果

問題 No.2867 NOT FOUND 404 Again
ユーザー flippergo
提出日時 2025-03-07 21:07:15
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,534 bytes
コンパイル時間 266 ms
コンパイル使用メモリ 82,836 KB
実行使用メモリ 812,912 KB
最終ジャッジ日時 2025-03-07 21:07:22
合計ジャッジ時間 5,287 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 MLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353
A = list(input().strip())
N = len(A)
if N<3:
    print("".join(A))
else:
    A = ["0"]+A
    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