結果

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

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    S = data[1]
    
    # Precompute prefix sums for sum_mod and number of '?'
    pre_mod = [0] * (N + 1)
    pre_q = [0] * (N + 1)
    for i in range(1, N+1):
        c = S[i-1]
        if c == '?':
            pre_q[i] = pre_q[i-1] + 1
            pre_mod[i] = pre_mod[i-1]
        else:
            d = int(c)
            pre_mod[i] = (pre_mod[i-1] + d) % 3
            pre_q[i] = pre_q[i-1]
    
    # Precompute pow_dp[k][r] where r is 0,1,2
    max_k = N
    a, b, c = 4, 3, 3  # coefficients of f(x) = 4 + 3x +3x²
    pow_dp = [ [0]*3 for _ in range(max_k+1) ]
    pow_dp[0][0] = 1
    for k in range(1, max_k+1):
        for r in range(3):
            # Multiply by f(x): for each term x^r, multiply by 4, 3x, 3x²
            # and accumulate to new_r = (r + s) mod3 for s=0,1,2
            new_r0 = (pow_dp[k-1][r] * a) % MOD
            new_r1 = (pow_dp[k-1][r] * b) % MOD
            new_r2 = (pow_dp[k-1][r] * c) % MOD
            pow_dp[k][(r + 0) %3] = (pow_dp[k][(r +0) %3] + new_r0) % MOD
            pow_dp[k][(r +1) %3] = (pow_dp[k][(r +1) %3] + new_r1) % MOD
            pow_dp[k][(r +2) %3] = (pow_dp[k][(r +2) %3] + new_r2) % MOD
    
    # Calculate sum_f_part1: sum for k>0
    sum_f_part1 = 0
    for L in range(1, N+1):
        for R in range(L, N+1):
            k = pre_q[R] - pre_q[L-1]
            if k == 0:
                continue
            sum_mod = (pre_mod[R] - pre_mod[L-1]) % 3
            t = (-sum_mod) %3
            sum_f_part1 = (sum_f_part1 + pow_dp[k][t]) % MOD
    
    # Calculate sum_f_part2: sum for k=0 and sum_mod ==0
    sum_f_part2 = 0
    for L in range(1, N+1):
        for R in range(L, N+1):
            k = pre_q[R] - pre_q[L-1]
            if k !=0:
                continue
            sum_mod = (pre_mod[R] - pre_mod[L-1]) %3
            if sum_mod ==0:
                sum_f_part2 +=1
    
    total = (sum_f_part1 + sum_f_part2) % MOD
    print(total)
    
if __name__ == '__main__':
    main()
0