結果

問題 No.2215 Slide Subset Sum
ユーザー qwewe
提出日時 2025-05-14 13:19:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,455 bytes
コンパイル時間 908 ms
コンパイル使用メモリ 76,472 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-14 13:20:40
合計ジャッジ時間 6,404 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 2 TLE * 1 -- * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>
#include <stdexcept> // For potential exceptions, though not strictly needed by the final simple solution

// Define the modulus
const int MOD = 998244353;

// Function to compute (base^exp) % mod using binary exponentiation
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// Function to compute modular inverse using Fermat's Little Theorem
// Assumes mod is prime and n is not a multiple of mod
long long modInverse(long long n) {
    // Check for division by zero modulo MOD
    long long n_mod = n % MOD;
    if (n_mod < 0) n_mod += MOD; // Ensure n_mod is in [0, MOD-1]
    if (n_mod == 0) {
        // This case should ideally not happen in this problem logic unless K=1 and element=0?
        // Or if trying inverse logic that hits non-invertible cases.
        // The recompute logic avoids this issue.
        throw std::runtime_error("Division by zero modulo p");
    }
    // Compute inverse using Fermat's Little Theorem: a^(p-2) = a^(-1) (mod p) for prime p
    return power(n_mod, MOD - 2);
}


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

    int N; // Length of the sequence A
    int M; // Length of the subarrays (window size)
    int K; // Modulo value for the sum
    std::cin >> N >> M >> K;

    std::vector<int> A(N); // Sequence A
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
        // Constraint check: 0 <= A[i] < K. This implies A[i] % K = A[i].
    }

    // dp state vector: dp[j] stores the number of subsequences whose sum is congruent to j modulo K.
    // The size of the vector is K.
    std::vector<long long> dp(K);

    // Iterate through all possible starting positions k of the sliding window.
    // The window spans indices [k, k+M-1].
    // k runs from 0 to N-M (0-based indexing).
    for (int k = 0; k <= N - M; ++k) {
        
        // Reset the dp state for each new window.
        // Initialize dp array with 0s.
        dp.assign(K, 0);
        // Base case: The empty subsequence has a sum of 0. Its count is 1.
        dp[0] = 1; 

        // Process each element within the current window A[k...k+M-1].
        for (int i = k; i < k + M; ++i) {
            // Store the current dp state because we need to read from it while updating.
            std::vector<long long> current_dp = dp; 
            
            // Get the value of the current element A[i]. Since 0 <= A[i] < K, A[i] % K = A[i].
            int x = A[i]; 

            // Create a temporary vector to store the counts of subsequences formed by adding A[i].
            // shifted_dp[j] will represent the count of subsequences from the previous state (using A[k..i-1])
            // whose sum was (j - x) mod K. Adding A[i] to these results in sum j mod K.
            std::vector<long long> shifted_dp(K);
            for(int j=0; j<K; ++j) {
                // Calculate the index (j - x) mod K correctly, handling potential negative results.
                int prev_sum_idx = (j - x % K + K) % K; 
                shifted_dp[j] = current_dp[prev_sum_idx];
            }

            // Update the dp state for the current element A[i].
            // For each remainder j, the new count dp[j] is the sum of:
            // 1. Subsequences from A[k...i-1] that already sum to j mod K (counts stored in current_dp[j]). These don't include A[i].
            // 2. Subsequences from A[k...i-1] that sum to (j-x) mod K (counts stored in shifted_dp[j]). These subsequences now include A[i].
            for (int j = 0; j < K; ++j) {
                 dp[j] = (current_dp[j] + shifted_dp[j]) % MOD;
            }
        }
        
        // The final dp[0] contains the count of all subsequences (including the empty one) 
        // whose sum is a multiple of K.
        // The problem asks for non-empty subsequences. Since the empty subsequence always has sum 0,
        // we subtract 1 from dp[0].
        // We add MOD before taking modulo to ensure the result remains non-negative if dp[0] was 0 or 1.
        long long ans = (dp[0] - 1 + MOD) % MOD;
        
        // Output the answer for the current window starting at index k.
        std::cout << ans << "\n";
    }

    return 0;
}
0