To solve this problem, we need to count the number of pairs of people such that the sum of their values is a power of two.

Approach

1. Frequency Map: Use a frequency map (dictionary) to keep track of the count of values we have processed so far. This helps in efficiently checking if the complement of the current value (to form a power of two) exists in the processed values.
2. Power of Two Check: For each value, check all possible powers of two (up to a sufficiently large value, like (2^{31}) since it covers most practical sums). For each power of two (p), compute the complement as (p - current_value). If this complement exists in the frequency map, add the count of the complement to the result (since these are valid pairs where the first element was processed before the current element).
3. Update Frequency Map: After processing each value, update the frequency map to include the current value.

Solution Code

import sys
from collections import Counter

def count_pairs():
    data = sys.stdin.read().split()
    n = int(data[0])
    a = list(map(int, data[1:n+1]))

    freq = Counter()
    result = 0

    # Check up to 2^31 (since it's larger than most possible sums)
    for num in a:
        for k in range(32):  # 2^0 to 2^31
            power = 1 << k
            complement = power - num
            if complement in freq:
                result += freq[complement]
        freq[num] += 1

    print(result)

count_pairs()

Explanation

• Frequency Map: The frequency map (freq) stores how many times each value has been encountered so far. This allows O(1) average time complexity for lookups.
• Power of Two Check: For each number, we check all powers of two from (2^0) to (2^{31}). This ensures we cover all possible sums that could be powers of two.
• Efficiency: The algorithm runs in O(N * log(max_sum)) time, where N is the number of elements. Since we check only 32 powers of two per element, this is efficient even for large N (up to (10^6) elements).

This approach efficiently counts the valid pairs by leveraging the frequency map and checking all relevant powers of two, ensuring correctness and optimal performance.

作者声明:本文包含人工智能生成内容。