結果

問題 No.2019 Digits Filling for All Substrings
ユーザー qwewe
提出日時 2025-05-14 13:04:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 71 ms / 2,000 ms
コード長 4,813 bytes
コンパイル時間 264 ms
コンパイル使用メモリ 82,096 KB
実行使用メモリ 76,020 KB
最終ジャッジ日時 2025-05-14 13:06:32
合計ジャッジ時間 3,501 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Function to handle the main logic
def solve():
    N = int(sys.stdin.readline())
    S = sys.stdin.readline().strip()
    MOD = 998244353

    # Modular exponentiation (iterative Bignum friendly)
    def fast_pow(base, power):
        """
        Calculates (base^power) % MOD efficiently.
        """
        result = 1
        while power > 0:
            if power % 2 == 1:  # If power is odd
                result = (result * base) % MOD
            # Divide power by 2 and square base
            base = (base * base) % MOD
            power //= 2
        return result

    # Modular inverse using Fermat's Little Theorem
    # Requires MOD to be a prime number, which 998244353 is.
    def inverse(a):
        """
        Calculates modular multiplicative inverse of a under modulo MOD.
        """
        return fast_pow(a, MOD - 2)

    # Precompute modular inverses needed
    inv3 = inverse(3)   # Modular inverse of 3
    inv10 = inverse(10) # Modular inverse of 10

    # Precompute powers of 10 and inverse 10 modulo MOD
    # P10[k] stores 10^k % MOD
    # InvP10[k] stores (10^{-1})^k % MOD
    P10 = [1] * (N + 1)      
    InvP10 = [1] * (N + 1)   
    for i in range(1, N + 1):
        P10[i] = (P10[i-1] * 10) % MOD
        InvP10[i] = (InvP10[i-1] * inv10) % MOD

    # Compute prefix sums D and Q
    # D[i]: Stores the sum of fixed digits modulo 3 in the prefix S[0...i-1].
    #       '?' are treated as contributing 0 to this sum.
    # Q[i]: Stores the count of '?' characters in the prefix S[0...i-1].
    D = [0] * (N + 1) 
    Q = [0] * (N + 1) 
    for i in range(N):
        # Calculate D[i+1] based on D[i] and S[i]
        D[i+1] = D[i] # Initialize with previous prefix sum
        if S[i] != '?':
            # If it's a digit, add its value to the sum modulo 3
            D[i+1] = (D[i] + int(S[i])) % 3
        
        # Calculate Q[i+1] based on Q[i] and S[i]
        Q[i+1] = Q[i] # Initialize with previous prefix count
        if S[i] == '?':
            # If it's a '?', increment the count
            Q[i+1] += 1

    # Initialize cumulative sums P1 and P2 which form the total answer
    # P1 corresponds to the sum part involving powers of 10
    # P2 corresponds to the sum part involving the delta function based on remainders
    P1 = 0
    P2 = 0
    
    # CurrentSumInvP10 stores the sum: sum_{i=0}^{R-1} InvP10[Q[i]] % MOD
    # This is needed to calculate P1 efficiently.
    CurrentSumInvP10 = 0
    
    # counts[r] stores the count of indices i in {0, ..., R-1} 
    # such that D[i] % 3 == r. This is needed for P2.
    counts = [0] * 3 
    # Initialize counts array based on the empty prefix (index 0).
    # D[0] = 0, so the count for remainder 0 starts at 1.
    counts[0] = 1 

    # Iterate over all possible right endpoints R of substrings S[L:R] (1-based index)
    for R in range(1, N + 1):
        # === Part 1: Calculation related to P1 ===
        # Update the running sum of inverse powers of 10 based on Q values
        # Add the term corresponding to prefix ending at index R-1 (0-based index L-1 = R-1)
        CurrentSumInvP10 = (CurrentSumInvP10 + InvP10[Q[R-1]]) % MOD
        
        # Calculate Term1 for endpoint R. Term1 is P10[Q[R]] * CurrentSumInvP10
        # This corresponds to sum_{L=1..R} P10[Q[R] - Q[L-1]]
        Term1 = (P10[Q[R]] * CurrentSumInvP10) % MOD
        # Accumulate Term1 into P1
        P1 = (P1 + Term1) % MOD

        # === Part 2: Calculation related to P2 ===
        # Calculate Term2 for endpoint R. Term2 is related to sum_{L=1..R} delta(D[L-1], D[R])
        target_rem = D[R]  # D[R] is already modulo 3
        
        # Get the count of prefix sums D[i] (for i < R) having the same remainder as D[R]
        count_target_rem = counts[target_rem]
        
        # Calculate Term2 = (3 * count - R) mod MOD.
        # The formula is derived from properties of the delta function.
        Term2 = (3 * count_target_rem - R) % MOD
        # Accumulate Term2 into P2. Add MOD before taking modulo to handle potential negative values.
        P2 = (P2 + Term2 + MOD) % MOD 

        # === Update state for the next iteration (R+1) ===
        # The counts array needs to be updated to include the contribution of index R.
        # Increment the count for the remainder D[R] % 3.
        counts[D[R]] += 1 # This update prepares counts for the next iteration R+1
                          # No need for MOD here as counts are simple integers.

    # === Final Calculation ===
    # The total sum is derived from P1 and P2: Sum = (P1 + P2) * inv3 mod MOD
    TotalSum = (P1 + P2 + MOD) % MOD # Ensure P1+P2 is non-negative before multiplying by inv3
    FinalAns = (TotalSum * inv3) % MOD
    
    # Print the final answer
    print(FinalAns)

# Execute the solver function
solve()
0