結果

問題 No.2867 NOT FOUND 404 Again
コンテスト
ユーザー 刘俊
提出日時 2025-08-11 18:14:57
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,192 bytes
コンパイル時間 419 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 73,344 KB
最終ジャッジ日時 2025-08-11 18:15:01
合計ジャッジ時間 3,215 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 RE * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def solve(N):
    s = str(N)
    n = len(s)
    
    # 记忆化数组
    memo = {}
    
    def dp(pos, tight, last1, last2, started):
        # pos: 当前位置, tight: 是否受限, last1/last2: 前两位数字, started: 是否已经开始
        if pos == n:
            return 1 if started else 0
        
        if (pos, tight, last1, last2, started) in memo:
            return memo[(pos, tight, last1, last2, started)]
        
        limit = int(s[pos]) if tight else 9
        result = 0
        
        for digit in range(0, limit + 1):
            # 检查是否形成404
            if last2 == 4 and last1 == 0 and digit == 4:
                continue
            
            new_tight = tight and (digit == limit)
            new_started = started or (digit > 0)
            new_last1 = digit if new_started else -1
            new_last2 = last1 if new_started else -1
            
            result = (result + dp(pos + 1, new_tight, new_last1, new_last2, new_started)) % MOD
        
        memo[(pos, tight, last1, last2, started)] = result
        return result
    
    return dp(0, True, -1, -1, False)

N = input().strip()
print(solve(int(N)))
0