結果

問題 No.2019 Digits Filling for All Substrings
ユーザー lam6er
提出日時 2025-03-20 20:34:02
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,229 bytes
コンパイル時間 147 ms
コンパイル使用メモリ 82,548 KB
実行使用メモリ 55,712 KB
最終ジャッジ日時 2025-03-20 20:35:25
合計ジャッジ時間 4,143 ms
ジャッジサーバーID
（参考情報） 		judge4 / 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 prefix sums mod3 and prefix counts of '?'
    prefix_sum = [0] * (N + 1)
    prefix_q = [0] * (N + 1)
    for i in range(N):
        c = S[i]
        prefix_sum[i+1] = prefix_sum[i] + (int(c) if c != '?' else 0)
        prefix_q[i+1] = prefix_q[i] + (1 if c == '?' else 0)
    # Convert prefix_sum to mod3
    for i in range(N+1):
        prefix_sum[i] %= 3

    # Precompute a[m][0], a[m][1], a[m][2] using DP
    max_m = N
    a = [[0] * 3 for _ in range(max_m + 1)]
    a[0][0] = 1
    for m in range(1, max_m + 1):
        a0_prev, a1_prev, a2_prev = a[m-1]
        a0_new = (4 * a0_prev + 3 * a1_prev + 3 * a2_prev) % MOD
        a1_new = (3 * a0_prev + 4 * a1_prev + 3 * a2_prev) % MOD
        a2_new = (3 * a0_prev + 3 * a1_prev + 4 * a2_prev) % MOD
        a[m][0] = a0_new
        a[m][1] = a1_new
        a[m][2] = a2_new

    from collections import defaultdict
    # We will track for each q_prev and s_prev, the count
    freq = defaultdict(lambda: defaultdict(int))
    # Initialize: before processing any characters, L=0 has q_prev=0, s_prev=0
    freq[0][0] = 1

    total = 0

    for R in range(1, N+1):
        current_q = prefix_q[R]
        current_s = prefix_sum[R] % 3

        # Contributions from all previous L, where L ranges from 0 to R-1
        # [L+1, R]
        # Iterate through all q_prev in freq
        new_total = 0
        q_prev_list = list(freq.keys())
        for q_prev in q_prev_list:
            if q_prev > current_q:
                continue
            m = current_q - q_prev
            if m < 0 or m > max_m:
                continue
            # For each s_prev in 0,1,2
            for s_prev in [0, 1, 2]:
                count = freq[q_prev][s_prev]
                if count == 0:
                    continue
                t = (s_prev - current_s) % 3
                new_total = (new_total + count * a[m][t]) % MOD
        total = (total + new_total) % MOD

        # Add current q and s to freq
        freq[current_q][current_s] = (freq[current_q][current_s] + 1) % MOD

    print(total % MOD)

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