#1084000 (C++17) No.1538 引きこもりさんは引き算が得意。

• 問題: No.1538 引きこもりさんは引き算が得意。
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:13:49
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 8,999 bytes
• コンパイル時間: 949 ms
• コンパイル使用メモリ: 105,916 KB
• 実行使用メモリ: 7,848 KB
• 最終ジャッジ日時: 2025-05-14 13:14:38
• 合計ジャッジ時間: 2,833 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 46 WA * 8

ソースコード

#include <iostream>
#include <vector>
#include <numeric> // Required for std::gcd (available since C++17)
#include <cmath>   // Required for std::abs
#include <unordered_map>
#include <vector>  // Make sure vector header is included

// Function to compute the greatest common divisor (GCD) of two numbers.
// Handles negative inputs by taking absolute values first.
// Relies on std::gcd available since C++17.
// If using an older standard, a custom implementation like Euclidean algorithm would be needed.
/*
long long custom_gcd(long long a, long long b) {
    a = std::abs(a);
    b = std::abs(b);
    while (b) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}
*/

// Function to compute GCD of all elements in a vector A.
// Handles potential 0 values correctly. The GCD of a set containing 0 and some non-zero numbers
// is the GCD of the non-zero numbers. GCD involving only 0 is 0.
long long calculate_vec_gcd(const std::vector<long long>& A) {
    if (A.empty()) {
        return 0; // Define GCD of empty set as 0
    }
    long long res = 0; 
    for (long long x : A) {
        // std::gcd(a, 0) returns std::abs(a). This property helps compute GCD correctly.
        // It effectively initializes `res` with the absolute value of the first non-zero element 
        // and then computes GCD iteratively.
        res = std::gcd(res, std::abs(x)); 
    }
    // If all elements in A are 0, the result will be 0.
    // Otherwise, it's the GCD of the absolute values of the non-zero elements.
    return res;
}

// Global variables accessible by DFS functions
std::vector<long long> A; // Stores the input array A
int N;                    // Number of elements in A
long long K;              // The target value K
int N1;                   // Size of the first half of A (N / 2)

// map_L stores sums generated from the first half of A (indices 0 to N1-1).
// Key: a possible sum value.
// Value: a boolean flag. `true` if this sum can ONLY be formed using all zero coefficients
// (this is only possible if the sum itself is 0). `false` if this sum can be formed using
// at least one non-zero coefficient (+1 or -1).
std::unordered_map<long long, bool> map_L;

bool found = false; // Global flag set to true once a valid representation of K is found

// Depth First Search function to generate sums for the first half of array A.
// index: current element index being considered (from 0 up to N1-1).
// current_sum: the sum accumulated so far along the current path.
// all_zeros: boolean flag, true if all coefficients used so far on this path are 0.
void generate_sums_L(int index, long long current_sum, bool all_zeros) {
    // Base case: If we have considered all elements in the first half
    if (index == N1) { 
        // Check if this sum is already in the map
        auto it = map_L.find(current_sum);
        if (it == map_L.end()) {
            // If this sum value is encountered for the first time, insert it with its all_zeros flag.
            map_L[current_sum] = all_zeros;
        } else {
            // If this sum value already exists, update its flag.
            // The flag remains true only if BOTH the existing ways AND this new way use all_zeros.
            // If *any* path generating this sum used non-zero coefficients, the flag becomes false.
             it->second = it->second && all_zeros; 
        }
        return; // End this path of recursion
    }

    // Recursive calls for the next index (index + 1):
    // Option 1: Use coefficient 0 for A[index]. The 'all_zeros' state doesn't change.
    generate_sums_L(index + 1, current_sum, all_zeros); 

    // Option 2: Use coefficient +1 for A[index]. This path now uses a non-zero coefficient.
    generate_sums_L(index + 1, current_sum + A[index], false); 

    // Option 3: Use coefficient -1 for A[index]. This path also uses a non-zero coefficient.
    generate_sums_L(index + 1, current_sum - A[index], false); 
}

// Depth First Search function to generate sums for the second half of array A and check for matches.
// index: current element index being considered (from N1 up to N-1).
// current_sum: the sum accumulated so far for the second half along the current path.
// all_zeros_R: boolean flag, true if all coefficients used so far in the second half on this path are 0.
void generate_sums_R(int index, long long current_sum, bool all_zeros_R) {
    // Optimization: If a solution has already been found, stop exploring further paths.
    if (found) return; 

    // Base case: If we have considered all elements in the second half (reached index N)
    if (index == N) { 
        // Calculate the required sum from the first half to achieve the target K
        long long target_sum = K - current_sum; 
        
        // Check if this required sum (target_sum) exists in the map generated from the first half
        auto it = map_L.find(target_sum);
        if (it != map_L.end()) { 
            // If target_sum exists in map_L, get its associated all_zeros flag.
            bool all_zeros_L = it->second; 
            
            // A representation K = S1 + S2 is valid if it uses at least one non-zero coefficient overall.
            // This condition is met if NOT (both S1 came from all_zeros=true AND S2 came from all_zeros_R=true).
            // Equivalent to: at least one of them came from a path with non-zero coefficients.
            if (!all_zeros_L || !all_zeros_R) {
                found = true; // Mark that a valid solution is found
            }
        }
        return; // End this path of recursion
    }

    // Recursive calls for the next index (index + 1) in the second half:
    // Option 1: Use coefficient 0 for A[index]. The 'all_zeros_R' state remains the same.
    generate_sums_R(index + 1, current_sum, all_zeros_R); 
    if (found) return; // Optimization check after recursive call returns

    // Option 2: Use coefficient +1 for A[index]. Sets 'all_zeros_R' to false for this path.
    generate_sums_R(index + 1, current_sum + A[index], false); 
     if (found) return; // Optimization check

    // Option 3: Use coefficient -1 for A[index]. Sets 'all_zeros_R' to false for this path.
    generate_sums_R(index + 1, current_sum - A[index], false); 
     // No need to check 'found' after the last recursive call in the function body, it's checked at the top.
}


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

    // Read problem input N and K
    std::cin >> N >> K;
    A.resize(N);
    bool all_input_elements_are_zero = true; // Flag to track if all A[i] are 0
    // Read the N integers into vector A
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
        if (A[i] != 0) {
            all_input_elements_are_zero = false; // Set flag to false if any non-zero element found
        }
    }

    // Handle the edge case where all input numbers A[i] are 0.
    if (all_input_elements_are_zero) {
        // If all A_i are 0, any linear combination $\sum c_i A_i$ results in 0.
        // The only value possible is 0.
        if (K == 0) {
            // We can achieve K=0. E.g., take A_1 with coefficient +1. The sum is 1*0=0. The subset {1} is non-empty.
            std::cout << "Yes" << std::endl; 
        } else {
            // If K is non-zero, it's impossible to achieve it from only zeros.
            std::cout << "No" << std::endl; 
        }
        return 0; // Exit program after handling this edge case
    }

    // Calculate the GCD of the absolute values of all elements in A.
    long long common_divisor = calculate_vec_gcd(A);

    // Apply the necessary condition based on GCD.
    // Any achievable number must be divisible by the GCD of the initial numbers.
    // This check is only meaningful if common_divisor is not 0 (i.e., not all A_i are 0).
    if (common_divisor != 0) { 
        // If K is not divisible by the common_divisor, it's impossible to form K.
        if (K % common_divisor != 0) {
            std::cout << "No" << std::endl;
            return 0; // Exit program
        }
    } 
    // Note: If common_divisor is 0, it means all A_i are 0, which was already handled.
    
    // Proceed with the Meet-in-the-Middle approach.
    N1 = N / 2; // Define the split point: first half has N1 elements (0..N1-1)

    // Phase 1: Generate all possible sums for the first half and store results in map_L.
    generate_sums_L(0, 0, true); // Start DFS from index 0, initial sum 0, initially all_zeros is true.

    // Phase 2: Generate sums for the second half and check against map_L if K can be formed.
    // Start DFS for the second half from index N1, initial sum 0, initially all_zeros_R is true.
    generate_sums_R(N1, 0, true); 

    // After exploring possibilities, output the final result based on the 'found' flag.
    if (found) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }

    return 0; // Indicate successful execution
}