結果
| 問題 |
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
}