To solve this problem, we need to find the number of subsets of a given set of pairs such that the XOR of all first elements in the subset is zero and the XOR of all second elements in the subset is zero.

Approach

1. Problem Analysis: Each pair (a_i, b_i) can be represented as a single 60-bit number by concatenating the bits of a_i (30 bits) and b_i (30 bits). This allows us to treat each pair as a vector in a 60-dimensional vector space over GF(2) (binary field).
2. Linear Basis: We use a linear basis to find the rank of the set of vectors. The rank of the basis gives the number of linearly independent vectors.
3. Count Subsets: The number of valid subsets (including the empty subset) is given by (2^{(n - r)}) where (n) is the number of elements and (r) is the rank of the linear basis. This is because each linearly dependent vector adds a factor of 2 to the number of valid subsets.

Solution Code

MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    basis = [0] * 60  # For 60 bits (30 for a, 30 for b)

    index = 1
    for _ in range(n):
        a = int(data[index])
        b = int(data[index + 1])
        index += 2
        x = (a << 30) | b  # Combine a and b into a 60-bit number

        # Insert x into the linear basis
        for i in reversed(range(60)):
            if (x >> i) & 1:
                if basis[i] == 0:
                    basis[i] = x
                    break
                else:
                    x ^= basis[i]

    # Calculate the rank of the basis
    rank = sum(1 for num in basis if num != 0)

    # The number of valid subsets is 2^(n - rank) mod MOD
    result = pow(2, n - rank, MOD)
    print(result)

if __name__ == "__main__":
    main()

Explanation

1. Representation: Each pair (a_i, b_i) is converted into a 60-bit number by shifting a_i left by 30 bits and OR-ing with b_i. This allows us to handle each pair as a single entity.
2. Linear Basis Construction: For each 60-bit number, we insert it into the linear basis. If the number is non-zero, we adjust it using existing basis elements to maintain the basis properties.
3. Rank Calculation: The rank of the basis is the count of non-zero elements in the basis array.
4. Result: The number of valid subsets is (2^{(n - rank)}) modulo (10^9 + 7). This accounts for all subsets where the XOR of both elements in the pairs is zero, including the empty subset.

This approach efficiently handles the problem using linear algebra over GF(2), ensuring optimal performance even for large input sizes. The time complexity is O(n * 60), which is feasible for most programming contest constraints.

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