#1083687 (C++17) No.868 ハイパー部分和問題

• 問題: No.868 ハイパー部分和問題
• ユーザー: qwewe
• 提出日時: 2025-05-14 12:55:54
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 7,475 bytes
• コンパイル時間: 623 ms
• コンパイル使用メモリ: 77,124 KB
• 実行使用メモリ: 7,844 KB
• 最終ジャッジ日時: 2025-05-14 12:57:49
• 合計ジャッジ時間: 17,435 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
sample	AC * 2
other	AC * 37 WA * 1

ソースコード

#include <iostream>
#include <vector>
#include <numeric>

// Define the modulo constant
// Using a common prime modulus for competitive programming.
const int MOD = 998244353;

// Function to compute (base^exp) % mod using binary exponentiation
// This is efficient for large exponents.
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD; // Ensure base is within modulo range
    while (exp > 0) {
        // If exponent is odd, multiply result with base
        if (exp % 2 == 1) res = (res * base) % MOD;
        // Square the base and halve the exponent
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// Function to compute modular inverse using Fermat's Little Theorem
// This works because MOD is a prime number.
// The modular inverse of n is n^(MOD-2) % MOD.
long long modInverse(long long n) {
     // Check if n is divisible by MOD. If so, inverse doesn't exist.
     // This handles cases like n=0 or n being a multiple of MOD.
     if (n % MOD == 0) {
         // Error case: inverse does not exist.
         // In this problem, we only need the inverse of 2. Since MOD is odd, 2 is not divisible by MOD.
         // So this check is mostly for robustness.
         return -1; // Indicates an error or non-existence.
     }
    // Calculate n^(MOD-2) % MOD
    return power(n, MOD - 2);
}

// Precompute modular inverse of 2, as it's used when handling elements with value 0.
// Initialized to -1 to indicate it hasn't been computed yet.
long long inv2 = -1; 

// Global vector to store polynomial coefficients. poly[s] stores the number of ways to form sum s.
// We only care about whether the count is non-zero, but tracking counts modulo MOD allows reversibility.
std::vector<int> poly;
// Global variable for the target sum K.
int K;

/**
 * @brief Adds the effect of an element with value A_val to the subset sums polynomial.
 *
 * This function updates the polynomial P(x) representing achievable sums to P(x) * (1 + x^A_val).
 * This corresponds to considering the subsets including A_val and those not including it.
 * The update rule is p_new[s] = p[s] + p[s - A_val].
 *
 * @param A_val The value of the element being added.
 */
void add_val(int A_val) {
    // Handle the special case where the element value is 0.
    if (A_val == 0) {
        // Adding 0 doesn't change the sum, but doubles the number of ways to achieve existing sums.
        // Equivalent to multiplying the polynomial by (1 + x^0) = (1 + 1) = 2.
        for (int i = 0; i <= K; ++i) {
            // Multiply each coefficient by 2 modulo MOD.
            poly[i] = (int)((poly[i] * 2LL) % MOD);
        }
        return;
    }
    // If A_val > K, including it in a subset will always result in a sum greater than K.
    // Thus, it doesn't affect the coefficients up to x^K.
    // P(x) * (1 + x^A_val) mod x^(K+1) = P(x) mod x^(K+1). No operation needed.
    if (A_val > K) return; 

    // Update the polynomial coefficients using the dynamic programming relation.
    // We iterate s backwards from K down to A_val to ensure that we use the coefficient poly[s - A_val]
    // from the *previous* state (before it was updated in the current step).
    for (int s = K; s >= A_val; --s) {
        // p_new[s] = (p_old[s] + p_old[s - A_val]) % MOD
        poly[s] = (int)((poly[s] + (long long)poly[s - A_val]) % MOD);
    }
}

/**
 * @brief Removes the effect of an element with value A_val from the subset sums polynomial.
 *
 * This function updates the polynomial P(x) to P(x) / (1 + x^A_val).
 * This reverses the operation performed by add_val.
 * The update rule is derived from P(x) = P_new(x) * (1 + x^A_val), which gives P_new(x) = P(x) / (1 + x^A_val).
 * Let P_new(x) = Q(x). Then P(x) = Q(x) + x^A_val * Q(x).
 * Coefficient-wise, p_s = q_s + q_{s - A_val}. This gives q_s = p_s - q_{s - A_val}.
 *
 * @param A_val The value of the element being removed.
 */
void remove_val(int A_val) {
     // Handle the special case where the element value is 0.
     if (A_val == 0) {
        // Removing 0 is equivalent to dividing the polynomial by (1 + x^0) = 2.
        // Multiply each coefficient by the modular inverse of 2.
        // Compute inv2 once if it hasn't been computed yet.
        if (inv2 == -1) inv2 = modInverse(2); 
        for (int i = 0; i <= K; ++i) {
            // Multiply by inv2 modulo MOD. Use long long for intermediate product.
            poly[i] = (int)(((long long)poly[i] * inv2) % MOD);
        }
        return;
    }
    // If A_val > K, removing it has no effect on coefficients up to x^K,
    // because it wasn't affecting them in the first place.
    // P(x) / (1 + x^A_val) mod x^(K+1) = P(x) / 1 mod x^(K+1) = P(x). No operation needed.
    if (A_val > K) return;

    // Compute the new coefficients q_s = p_s - q_{s - A_val}.
    // Iterate s forwards from 0 to K. When computing q_s, we need q_{s - A_val}.
    // If we update poly[s] in place, the value poly[s - A_val] will hold the already computed q_{s - A_val}.
    for (int s = 0; s <= K; ++s) {
        // Check if s >= A_val to avoid accessing negative indices.
        if (s >= A_val) {
             // Calculate q_s = (p_s - q_{s - A_val}) % MOD.
             // Add MOD before taking modulo to handle potential negative results from subtraction.
             // Use long long for intermediate subtraction to avoid potential underflow/wrap-around issues before adding MOD.
             poly[s] = (int)(((long long)poly[s] - poly[s - A_val] + MOD) % MOD);
        }
        // If s < A_val, then q_{s - A_val} is considered 0 (no terms with negative index).
        // So q_s = p_s. Since poly[s] already holds p_s, no change is needed.
    }
}


int main() {
    // Optimize standard I/O operations for speed.
    std::ios_base::sync_with_stdio(false); 
    std::cin.tie(NULL);                   

    int N; // Number of elements in the sequence
    std::cin >> N >> K; // Read N and target sum K

    std::vector<int> A(N); // Vector to store the current sequence elements
    poly.resize(K + 1, 0); // Resize polynomial coefficient vector to hold coefficients up to K
    poly[0] = 1; // Initialize P(x) = 1, representing the empty set which sums to 0 in one way.

    // Process the initial array elements
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i]; // Read the i-th element
        add_val(A[i]);    // Incorporate its effect into the polynomial
    }

    int Q; // Number of updates/queries
    std::cin >> Q;

    // Precompute modular inverse of 2 if needed (for elements with value 0).
    inv2 = modInverse(2); 

    // Process each query
    for (int i = 0; i < Q; ++i) {
        int x; // 1-based index of the element to change
        int v; // The new value for the element
        std::cin >> x >> v;
        --x; // Convert to 0-based index for vector access

        remove_val(A[x]); // Remove the effect of the old value A[x] from the polynomial
        A[x] = v;         // Update the value in the array
        add_val(A[x]);    // Add the effect of the new value v to the polynomial

        // After update, check if the coefficient of x^K (poly[K]) is non-zero.
        // A non-zero coefficient means sum K is achievable.
        if (poly[K] != 0) {
            std::cout << 1 << "\n"; // Output 1 if K is achievable
        } else {
            std::cout << 0 << "\n"; // Output 0 otherwise
        }
    }

    return 0; // Indicate successful execution
}