結果

問題 No.3105 Parallel Connection and Spanning Trees
ユーザー qwewe
提出日時 2025-05-14 12:59:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,489 bytes
コンパイル時間 2,733 ms
コンパイル使用メモリ 103,532 KB
実行使用メモリ 11,040 KB
最終ジャッジ日時 2025-05-14 13:02:37
合計ジャッジ時間 7,629 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 3 TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>
#include <cmath>
#include <set> // Using std::set for ordered sums, useful for finding minimum absolute value
#include <algorithm>

// Function to calculate the 'evenness' for a given subsequence.
// Evenness is the minimum absolute value of the sum obtainable by multiplying each element by 1 or -1.
long long calculate_evenness(const std::vector<long long>& subsequence, long long P) {
    // If the subsequence is empty, its evenness is not well-defined in the context of the problem statement 
    // (which asks for non-empty subsequences). However, if called with an empty sequence, return 0.
    if (subsequence.empty()) {
        return 0; 
    }

    // Use std::set to keep track of reachable sums.
    // std::set automatically handles duplicates and keeps elements sorted, which might be helpful.
    // However, for potentially large numbers of sums, performance might be an issue compared to unordered_set.
    // Given N <= 300, the number of elements in a subsequence is at most 300.
    // The number of reachable sums can be up to 2^k where k is subsequence length. Max 2^300, too large.
    // This implies the brute-force approach of generating all sums for each subsequence is too slow for N=300.
    // But, the constraint "Sum of N over all test cases does not exceed 6000" suggests that large N is rare.
    // Maybe N is small enough for most cases such that 2^N is feasible within the time limit.
    // Let's stick to the set-based approach.
    
    std::set<long long> reachable_sums;
    reachable_sums.insert(0); // Start with sum 0 (representing choice before considering any element)

    // Iterate through each element in the subsequence
    for (long long x : subsequence) {
        std::set<long long> next_sums; // Temporary set to store sums for the next step

        // For each sum 's' reachable so far, calculate the new sums 's+x' and 's-x'.
        for (long long s : reachable_sums) {
            next_sums.insert(s + x);
            next_sums.insert(s - x);

            // Optimization: If the set becomes too large, we might run into Time Limit Exceeded or Memory Limit Exceeded.
            // However, standard problem solutions usually don't require such heuristics unless specified.
            // Let's proceed without explicit size limit first.
            // The problem constraints and type suggest either N is small enough, or there's a polynomial time DP solution.
            // Since the polynomial solution is not obvious, let's hope N is small enough on average.
        }
         // Move the newly computed sums to become the current reachable sums. std::move can be efficient.
        reachable_sums = std::move(next_sums); 
    }

    // After processing all elements, find the minimum absolute value among reachable sums.
    long long min_abs_val = -1; // Initialize with -1 to act as positive infinity marker

    // Check if 0 is reachable. If yes, the minimum absolute sum is 0.
    bool has_zero = reachable_sums.count(0);

    if (has_zero) {
        return 0;
    } else {
         // If 0 is not reachable, find the minimum absolute value among non-zero sums.
         // Since the subsequence is non-empty and elements A_i >= 1, the reachable_sums set must contain non-zero values.
         for (long long s : reachable_sums) {
             // Calculate absolute value
             long long current_abs = std::abs(s);
             // Update minimum absolute value found so far
             if (min_abs_val == -1 || current_abs < min_abs_val) {
                 min_abs_val = current_abs;
             }
         }
         // This case should theoretically not happen for non-empty subsequences with positive elements if 0 is not reachable.
         // If it happens, it indicates an issue or edge case not handled.
         if (min_abs_val == -1) return 0; // Default return, though ideally unreachable.
         return min_abs_val;
    }
}


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

    int T; // Number of test cases
    std::cin >> T;
    while (T--) {
        int N; // Length of the arithmetic progression A
        long long P; // Modulo P
        std::cin >> N >> P;
        std::vector<long long> A(N); // The arithmetic progression
        for (int i = 0; i < N; ++i) {
            std::cin >> A[i];
        }

        long long total_evenness_sum = 0; // Accumulator for the sum of evenness values

        // Iterate through all possible non-empty subsequences of A.
        // There are 2^N - 1 non-empty subsequences. We can represent them using bitmasks from 1 to 2^N - 1.
        for (int k = 1; k < (1 << N); ++k) {
            std::vector<long long> subsequence; // Current subsequence
            // Build the subsequence based on the bits set in k
            for (int i = 0; i < N; ++i) {
                if ((k >> i) & 1) { // Check if the i-th bit is set
                    subsequence.push_back(A[i]);
                }
            }
            
            // Calculate the evenness for the current subsequence
            long long evenness = calculate_evenness(subsequence, P);
            
            // Add the evenness to the total sum, modulo P
            total_evenness_sum = (total_evenness_sum + evenness) % P;
        }

        // Output the result for the current test case
        std::cout << total_evenness_sum << "\n";
    }
    return 0;
}
0