結果

問題 No.2867 NOT FOUND 404 Again
ユーザー flippergo
提出日時 2025-03-08 08:25:15
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,746 bytes
コンパイル時間 511 ms
コンパイル使用メモリ 81,904 KB
実行使用メモリ 148,272 KB
最終ジャッジ日時 2025-03-08 08:25:22
合計ジャッジ時間 6,964 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 TLE * 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(2)]
    dp[2%2][A[2]][A[1]][0] = 1
    for j1 in range(A[2]):
        dp[2%2][j1][A[1]][1] = 1
    for j1 in range(10):
        for j2 in range(A[1]):
            dp[2%2][j1][j2][1] = 1
    for i in range(2,N):
        for j1 in range(10):
            for j2 in range(10):
                for s in range(2):
                    dp[(i+1)%2][j1][j2][s] = 0
        for j1 in range(10):
            for j2 in range(10):
                if j1!=0 or j2!=4:
                    for k1 in range(10):
                        dp[(i+1)%2][k1][j1][1] = (dp[(i+1)%2][k1][j1][1]+dp[i%2][j1][j2][1])%MOD
                    dp[(i+1)%2][A[i+1]][j1][0] = (dp[(i+1)%2][A[i+1]][j1][0]+dp[i%2][j1][j2][0])%MOD
                    for k1 in range(A[i+1]):
                        dp[(i+1)%2][k1][j1][1] = (dp[(i+1)%2][k1][j1][1]+dp[i%2][j1][j2][0])%MOD
                else:
                    for k1 in range(10):
                        if k1==4:continue
                        dp[(i+1)%2][k1][j1][1] = (dp[(i+1)%2][k1][j1][1]+dp[i%2][j1][j2][1])%MOD
                    if A[i+1]!=4:
                        dp[(i+1)%2][A[i+1]][j1][0] = (dp[(i+1)%2][A[i+1]][j1][0]+dp[i%2][j1][j2][0])%MOD
                    for k1 in range(A[i+1]):
                        if k1==4:continue
                        dp[(i+1)%2][k1][j1][1] = (dp[(i+1)%2][k1][j1][1]+dp[i%2][j1][j2][0])%MOD
    ans = 0
    for j1 in range(10):
        for j2 in range(10):
            ans = (ans+dp[N%2][j1][j2][0]+dp[N%2][j1][j2][1])%MOD
    print((ans-1)%MOD)
0