結果

問題 No.2807 Have Another Go (Easy)
ユーザー qwewe
提出日時 2025-05-14 13:01:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,790 bytes
コンパイル時間 963 ms
コンパイル使用メモリ 79,472 KB
実行使用メモリ 33,580 KB
最終ジャッジ日時 2025-05-14 13:03:39
合計ジャッジ時間 5,498 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm> // For std::max

using namespace std;

// Use long long for N potentially large
long long N;
int M; // M is given as 2 in this version of the problem
int k;
vector<long long> C; // Stores the C_i values for the k queries

const long long MOD = 998244353; // The modulus for calculations

int main() {
    // Faster I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Read input N, M, k
    cin >> N >> M >> k;

    // Read the k values of C_i
    C.resize(k);
    for (int i = 0; i < k; ++i) {
        cin >> C[i];
    }

    // Calculate the termination threshold NM. Since M=2, NM = 2N.
    long long NM = N * M; 
    // Problem constraints state N >= 6, so NM >= 12. This avoids edge cases with small NM.

    // --- Step 1: Calculate the DP table for total ways ---
    // dp[x] stores the number of ways to reach state X=x without terminating before.
    vector<long long> dp(NM);
    dp[0] = 1; // Base case: There is 1 way to be at state 0 initially.
    
    // Fill the DP table up to state NM-1
    for (long long x = 1; x < NM; ++x) {
        dp[x] = 0; // Initialize ways to reach state x
        // Sum contributions from previous states reachable by rolling 1 to 6
        for (int d = 1; d <= 6; ++d) {
            if (x - d >= 0) { // Check if the previous state x-d is valid (non-negative)
                dp[x] = (dp[x] + dp[x - d]) % MOD; // Add ways from dp[x-d] modulo MOD
            }
        }
    }

    // --- Step 2: Calculate the total number of terminating sequences ---
    long long T_total = 0;
    // cnt[x] will store the number of dice rolls 'd' (1 to 6) that cause termination from state x (i.e., x+d >= NM)
    vector<long long> cnt(NM); 
    
    // Calculate cnt[x] and T_total contribution for relevant states x.
    // Relevant states are those from which termination is possible in one step: NM-6 to NM-1.
    // Iterate from NM-1 down to max(0LL, NM-6) to cover these states. max(0LL, ...) handles NM < 6 case (although not needed here N>=6).
    for (long long x = NM - 1; x >= max(0LL, NM - 6); --x) {
        long long current_cnt = 0; // Count terminating rolls from state x
        for(int d = 1; d <= 6; ++d) {
            if (x + d >= NM) { // Check if rolling 'd' leads to termination
                current_cnt++;
            }
        }
        cnt[x] = current_cnt; // Store the count for state x
        
        // Add the contribution of paths ending through state x to T_total
        // dp[x] ways to reach state x, cnt[x] ways to terminate from x
        T_total = (T_total + dp[x] * cnt[x]) % MOD;
    }
    
    // Problem constraints: 1 <= C_i < N. This implies C_i % N != 0.
    // The initial state X_0=0 is always added to Y. Since 0 % N = 0, and C_i % N != 0,
    // the condition X_0 % N != C_i always holds.

    // --- Step 3: For each query C_i, calculate the answer ---
    vector<long long> results; // Store results for each query
    results.reserve(k); // Reserve space for efficiency
    
    // dp_noC[x] will store the number of ways to reach state x such that no state Y[j] satisfies Y[j] % N == C_i
    // This DP table is reused for each query C_i.
    vector<long long> dp_noC(NM); 

    for (int i = 0; i < k; ++i) {
        long long current_C = C[i]; // The C value for the current query

        // --- Calculate dp_noC table for the current C_i ---
        // Base case: dp_noC[0] = 1. As discussed, X_0=0 never violates the condition.
        dp_noC[0] = 1; 
        for (long long x = 1; x < NM; ++x) {
            dp_noC[x] = 0; // Initialize ways to reach state x under the condition
            for (int d = 1; d <= 6; ++d) {
                if (x - d >= 0) { // Check if previous state is valid
                    long long prev_state = x - d; // The state before rolling 'd'
                    
                    // The condition is on states in Y = [X_0, ..., X_{T-1}].
                    // When calculating ways to reach state X_t=x, the state X_{t-1}=prev_state is the last state added to Y.
                    // We must check if prev_state % N == current_C. If it is, this path is invalid for dp_noC.
                    if (prev_state % N != current_C) {
                         // If the condition is NOT violated by prev_state, add the ways from dp_noC[prev_state].
                         dp_noC[x] = (dp_noC[x] + dp_noC[prev_state]) % MOD;
                    }
                }
            }
        }

        // --- Calculate T_C^c: total ways for the complement event ---
        // T_C^c = Number of terminating sequences where for all Y[j], Y[j] % N != C_i.
        long long T_Cc = 0;
        // Sum over states x from which the game can terminate (NM-6 to NM-1)
        for (long long x = NM - 1; x >= max(0LL, NM - 6); --x) {
             // The last state added to Y is x (which is X_{T-1}).
             // This state x must also satisfy the condition x % N != C_i for the sequence to be counted in T_C^c.
            if (x % N != current_C) {
                 // If condition holds for x, add its contribution: dp_noC[x] ways to reach x satisfying condition * cnt[x] ways to terminate.
                 T_Cc = (T_Cc + dp_noC[x] * cnt[x]) % MOD; // Use precomputed cnt[x]
            }
        }

        // --- Final answer for C_i ---
        // The required answer is Total sequences - Complement sequences.
        // (T_total - T_Cc + MOD) % MOD handles potential negative result from subtraction.
        long long ans = (T_total - T_Cc + MOD) % MOD; 
        results.push_back(ans); // Store the answer for this query
    }

    // --- Step 4: Output results ---
    for (long long res : results) {
        cout << res << "\n";
    }

    return 0;
}
0