結果

問題 No.2019 Digits Filling for All Substrings
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:07:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 89 ms / 2,000 ms
コード長 1,391 bytes
コンパイル時間 201 ms
コンパイル使用メモリ 82,216 KB
実行使用メモリ 77,364 KB
最終ジャッジ日時 2025-06-12 14:07:57
合計ジャッジ時間 3,313 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    S = input[1]
    
    cnt = [4, 3, 3]  # cnt[0] = 4 digits (0,3,6,9), cnt[1] = 3 (1,4,7), cnt[2] = 3 (2,5,8)
    
    prev_dp = [0, 0, 0]
    total = 0
    
    for c in S:
        current_dp = [0, 0, 0]
        if c == '?':
            # For each previous remainder, distribute to new remainders based on t
            for r_prev in range(3):
                for t in range(3):
                    new_r = (r_prev + t) % 3
                    current_dp[new_r] = (current_dp[new_r] + prev_dp[r_prev] * cnt[t]) % MOD
            # Add the single character case: all possible digits
            for r in range(3):
                current_dp[r] = (current_dp[r] + cnt[r]) % MOD
        else:
            d = int(c)
            for r_prev in range(3):
                new_r = (r_prev + d) % 3
                current_dp[new_r] = (current_dp[new_r] + prev_dp[r_prev]) % MOD
            # Add single character case: d mod 3
            new_r = d % 3
            current_dp[new_r] = (current_dp[new_r] + 1) % MOD
        
        # Add the number of valid substrings ending at this position to the total
        total = (total + current_dp[0]) % MOD
        
        # Update previous DP
        prev_dp = current_dp.copy()
    
    print(total % MOD)

if __name__ == '__main__':
    main()
0