結果

問題 No.2807 Have Another Go (Easy)
ユーザー qwewe
提出日時 2025-05-14 13:14:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 106 ms / 3,000 ms
コード長 4,291 bytes
コンパイル時間 348 ms
コンパイル使用メモリ 82,960 KB
実行使用メモリ 77,056 KB
最終ジャッジ日時 2025-05-14 13:14:59
合計ジャッジ時間 5,851 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Set a reasonable recursion depth, although this solution is iterative.
# sys.setrecursionlimit(2000000) 

def solve():
    # Read input N, M, k
    N, M, k = map(int, sys.stdin.readline().split())
    # M is fixed to 2 for this problem version.
    # Read the list of query values C_i
    C = list(map(int, sys.stdin.readline().split()))

    # Define the modulus
    MOD = 998244353

    # The game ends when X >= NM. With M=2, this is X >= 2N.
    # We need to compute DP states up to X = 2N - 1.
    limit = 2 * N
    
    # DP array P to store the number of ways to reach state X=x. P[x] stores this count.
    # Size is 'limit' to store values for indices 0 to 2N-1.
    P = [0] * limit
    
    # Base case: There is 1 way to be at state X=0 initially (the starting state).
    if limit > 0:
        P[0] = 1
    
    # Calculate P[1]..P[6] using the basic DP definition: P[x] is the sum of ways to reach previous states P[x-d] for d=1..6.
    # For small x, P[x] = P[0] + P[1] + ... + P[x-1].
    current_sum = 1 # Initial sum is P[0] for calculating P[1]
    for x in range(1, min(7, limit)):
        P[x] = current_sum
        # Update the sum for the next iteration: add P[x] to it.
        current_sum = (current_sum + P[x]) % MOD

    # For x >= 7, we can use the optimized recurrence relation: P[x] = 2*P[x-1] - P[x-7].
    # This is derived from the characteristic equation of the linear recurrence P[x] = sum_{d=1..6} P[x-d].
    for x in range(7, limit):
        # Calculate P[x] using the recurrence. Ensure results stay within modulo.
        term1 = (2 * P[x-1]) % MOD
        term2 = P[x-7]
        P[x] = (term1 - term2 + MOD) % MOD # Add MOD before taking modulo to handle potential negative results

    # Precompute P(N) as it's needed for calculating E_i for each query.
    # Constraints N >= 6 ensure N < 2N, so P[N] is within the computed range.
    P_N = P[N] 
    
    results = []

    # Process each query C_i
    for C_i in C:
        # Constraints: 1 <= C_i < N. N >= 6.
        # Fetch required P values P(C_i) and P(C_i + N).
        # These indices are guaranteed to be valid (within [0, 2N-1]).
        P_Ci = P[C_i]
        P_Ci_plus_N = P[C_i + N]

        # Calculate the 'injection correction' term E_i = P(C_i+N) - P(C_i) * P(N) mod MOD.
        # This term represents the adjustment needed at state C_i+N due to the path constraint.
        E_i = (P_Ci_plus_N - (P_Ci * P_N % MOD) + MOD) % MOD

        # Initialize sums for the two parts of the final answer formula.
        # The answer is derived from inclusion-exclusion principle applied to paths,
        # simplified using properties of linear recurrences.
        # ANS_i = P(C_i) * Sum1 + E_i * Sum2
        sum1 = 0  # Corresponds to the term multiplied by P(C_i)
        sum2 = 0  # Corresponds to the term multiplied by E_i

        # The final answer involves summing contributions from states 2N-k for k=1..6.
        # The contribution weight is (7-k), representing the number of die rolls (from 1 to 6)
        # that would end the game from state 2N-k.
        for k in range(1, 7):
            weight = 7 - k # Weight for state 2N-k

            # Calculate contribution to sum1
            idx1 = limit - k - C_i # Index is 2N-k-Ci
            # This index represents the state relative to C_i.
            # Based on constraints, idx1 is always within [0, 2N-1].
            term1 = P[idx1]
            sum1 = (sum1 + term1 * weight) % MOD

            # Check condition N - k >= C_i for sum2 contribution.
            # This condition determines if the state 2N-k is >= C_i + N.
            if N - k >= C_i:
                idx2 = N - k - C_i # Index is N-k-Ci
                # This index represents the state relative to C_i + N.
                # It can be shown idx2 >= 0 under the condition N - k >= C_i.
                # Also idx2 < N < 2N, so it's within bounds.
                term2 = P[idx2]
                sum2 = (sum2 + term2 * weight) % MOD
        
        # Calculate the final answer for query C_i using the derived formula
        ans_i = (P_Ci * sum1 % MOD + E_i * sum2 % MOD) % MOD
        results.append(ans_i)

    # Print all computed results for the queries
    for res in results:
        print(res)

# Execute the main function
solve()
0