python-subset-xor-divisible-count

Answer

Key insight. Subset XOR is a linear map over GF(2): choosing subset S sends the indicator vector c ∈ F2^n to ⊕_{i∈S} a_i. This is a linear map from F2^n onto the span V = ⟨a₁,…,aₙ⟩ with dim V = rank ≤ 64. By the rank–nullity theorem, every v ∈ V has exactly 2^(n − rank) preimages, and values outside V have zero. So the answer for a query T is:

• 0 if T ∉ V
• 2^(n − rank) mod 1e9+7 if T ∈ V, T ≠ 0
• 2^(n − rank) − 1 mod 1e9+7 if T = 0 (subtract the empty subset)

The basis is built once with Gaussian elimination (triangular form: basis[b] has highest set bit b), and each query is a membership test by reduction in O(rank). Total complexity O(n·64 + q·64); the combinatorial factor 2^(n−rank) handles duplicates automatically.

Optimizations: dedupe via a set (values come from a pool of ≤ 64 distinct numbers) and early-exit once rank == 64 (full rank means every 64-bit value is reachable).

import sys

MOD = 1_000_000_007
MAX_BITS = 64  # unsigned 64-bit integers

def build_basis(arr):
    """Triangular GF(2) basis: basis[b] has highest set bit b."""
    basis = [0] * MAX_BITS
    rank = 0
    seen = set()
    for x in arr:
        if x == 0 or x in seen:
            continue               # zeros/duplicates never change the basis
        seen.add(x)
        y = x
        while y:
            b = y.bit_length() - 1
            nb = basis[b]
            if nb:
                y ^= nb            # clear leading bit, bits above b untouched
            else:
                basis[b] = y
                rank += 1
                break
        if rank == MAX_BITS:
            break                  # full rank: every 64-bit value reachable
    return basis, rank

def in_span(basis, t):
    """Membership test by reduction; O(rank) <= O(64)."""
    y = t
    while y:
        b = y.bit_length() - 1
        nb = basis[b]
        if not nb:
            return False
        y ^= nb
    return True

def solve():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    n, q = int(data[0]), int(data[1])
    arr = [int(tok) for tok in data[2:2 + n]]
    queries = data[2 + n:2 + n + q]

    basis, rank = build_basis(arr)
    factor = pow(2, n - rank, MOD)          # subsets per reachable value

    cache = {}
    out = []
    for tok in queries:
        t = int(tok)
        if t in cache:
            out.append(str(cache[t])); continue
        if t == 0:                          # 0 always reachable; drop empty subset
            ans = (factor - 1) % MOD
        elif in_span(basis, t):
            ans = factor
        else:
            ans = 0
        cache[t] = ans
        out.append(str(ans))
    sys.stdout.write("\n".join(out) + ("\n" if out else ""))

if __name__ == "__main__":
    solve()

Input format: line 1 = n q; next n integers = array; next q integers = targets; one answer per line. A naive 2^n enumeration, DP over the value space (2⁶⁴), or per-query basis rebuild will not scale — this runs in linear time.