結果

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

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    S = input[1]
    
    # Precompute dp[k][t] where t is 0,1,2
    max_k = N
    dp = [[0]*3 for _ in range(max_k+1)]
    dp[0][0] = 1
    for k in range(1, max_k+1):
        for t in range(3):
            total = 0
            for s in range(3):
                cnt = 4 if s == 0 else 3
                prev_t = (t - s) %3
                total += dp[k-1][prev_t] * cnt
                total %= MOD
            dp[k][t] = total
    
    # Precompute prefix sum mod3 and prefix count of '?'
    prefix_s = [0]*(N+1)
    prefix_q = [0]*(N+1)
    for i in range(1, N+1):
        c = S[i-1]
        if c == '?':
            prefix_q[i] = prefix_q[i-1] + 1
            prefix_s[i] = prefix_s[i-1]
        else:
            d = int(c)
            prefix_s[i] = (prefix_s[i-1] + d) %3
            prefix_q[i] = prefix_q[i-1]
    
    # Now, use a dictionary to track (s, q) counts
    from collections import defaultdict
    total = 0
    counter = defaultdict(int)
    counter[(0, 0)] = 1  # initial state: prefix 0, s=0, q=0
    
    for i in range(1, N+1):
        current_s = prefix_s[i]
        current_q = prefix_q[i]
        
        # Compute contribution for all possible s_prev and q_prev
        for s_prev in range(3):
            for q_prev in range(current_q +1):
                t = (3 - (current_s - s_prev) %3 ) %3
                k = current_q - q_prev
                if k <0:
                    continue
                if k > max_k:
                    continue
                # The number of substrings ending at i with s_sub and k '?'
                cnt = counter.get( (s_prev, q_prev), 0 )
                if cnt ==0:
                    continue
                contribution = (dp[k][t] * cnt) % MOD
                total = (total + contribution) % MOD
        
        # Update the counter with current_s and current_q
        key = (current_s, current_q)
        counter[key] = (counter.get(key, 0) + 1) % MOD
    
    print(total % MOD)

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