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.

（免责声明：本文为本网站出于传播商业信息之目的进行转载发布，不代表本网站的观点及立场。本文所涉文、图、音视频等资料的一切权利和法律责任归材料提供方所有和承担。本网站对此资讯文字、图片等所有信息的真实性不作任何保证或承诺，亦不构成任何购买、投资等建议，据此操作者风险自担。） 本文为转载内容，授权事宜请联系原著作权人，如有侵权，请联系本网进行删除。