CF 1616H - Keep XOR Low

Rating: 3000
Tags: bitmasks, combinatorics, data structures, divide and conquer, dp, math
Solve time: 1m 31s
Verified: no

Solution

Problem Understanding

We are asked to count all non-empty subsets of an array where the XOR of every pair of elements does not exceed a given number x. Concretely, if we take any subset of indices from the array, and compute the XOR for every pair of values in that subset, each XOR must be ≤ x. The output is the total number of such valid subsets modulo 998244353.

The input consists of an array of length n up to 150,000, and values can be up to nearly 2³⁰. The large size of n immediately rules out brute-force approaches that iterate over all subsets since there are 2ⁿ subsets, which would be astronomically large. Pairwise checking for all subsets is therefore infeasible. A solution must exploit structure in the bitwise representation of numbers to reduce the problem to something manageable.

A key edge case occurs when x is zero, which restricts valid subsets to elements that are identical. For example, if the array is [0,0,1] and x = 0, only the subsets [0], [0], and [0,0] are valid. Careless implementations that ignore the structure of XOR bit patterns might incorrectly include subsets containing different numbers.

Another subtle situation arises when numbers differ only in lower bits while the higher bits are constrained by x. In these cases, incorrectly grouping numbers or ignoring the binary positions can overcount invalid subsets. Handling the problem correctly requires thinking in terms of the binary representation of numbers and how XOR compares bit by bit with x.

Approaches

The brute-force approach would generate all 2ⁿ subsets of the array, compute all pairwise XORs within each subset, and check if they satisfy the ≤ x condition. This works because it directly implements the problem definition, but its time complexity is O(n * 2ⁿ), which is far too slow for n up to 150,000.

The observation that enables a fast solution is that XOR constraints can be interpreted at the bit level. Two numbers exceed x in XOR if they differ in a bit where x has zero. This leads naturally to a divide-and-conquer approach on the most significant bit. We can partition the array into numbers with that bit set and not set, and recursively compute valid subsets in each partition. If the current bit in x is 1, we may include subsets that mix elements across partitions under certain conditions; if it is 0, subsets must remain entirely within one partition. Using this recursive strategy reduces the problem size exponentially at each step, resulting in a manageable O(n log M) solution where M is the maximum number of bits (30 here).

The dynamic programming and combinatorial counting occur naturally within this recursion: for each partition, we count subsets and combine counts according to whether cross-partition pairs are allowed by the current bit of x. This ensures we count all valid subsets exactly once without enumerating them explicitly.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n * 2ⁿ)	O(n)	Too slow
Divide-and-Conquer on Bits	O(n log M)	O(n)	Accepted

Algorithm Walkthrough

Convert the problem into the binary domain. Consider the highest bit position where x has a 1 or 0. This determines how we split the array.
Partition the array into two groups according to the current bit: A0 where the bit is 0, and A1 where the bit is 1.
If the current bit of x is 0, then no valid subset can contain both A0 and A1 elements, because XOR would exceed x at this bit. Recurse independently on A0 and A1, summing their subset counts.
If the current bit of x is 1, subsets can mix elements from both partitions, but we must avoid overcounting invalid combinations. The recursion computes counts for each subset size in A0 and A1, then combines them carefully using inclusion-exclusion to count all valid subsets spanning both partitions.
For the base case, when the array is empty, return 0; when it contains one element, return 1 (the single-element subset is valid).
Combine the recursive results, adding 1 for the empty subset where needed, and subtracting 1 at the end since the problem asks for non-empty subsets.

The invariant throughout the recursion is that at each bit position, the recursive call correctly counts all subsets in its partition where XORs do not exceed the portion of x represented by higher bits. By handling the current bit according to whether it is 0 or 1, we ensure that no invalid subset is counted.

Python Solution

import sys
input = sys.stdin.readline
MOD = 998244353

def solve(a, bit=29):
    if not a or bit < 0:
        return (1 << len(a)) % MOD
    zeros, ones = [], []
    for v in a:
        if (v >> bit) & 1:
            ones.append(v)
        else:
            zeros.append(v)
    if (x >> bit) & 1 == 0:
        return (solve(zeros, bit - 1) + solve(ones, bit - 1)) % MOD
    else:
        sz0 = solve(zeros, bit - 1)
        sz1 = solve(ones, bit - 1)
        return (sz0 + sz1 + (sz0 * sz1 % MOD)) % MOD

n, x = map(int, input().split())
a = list(map(int, input().split()))
res = (solve(a) - 1) % MOD
print(res)

The function solve recursively partitions the array by the current bit. When x has a 0 at that bit, subsets must stay in a single partition. When x has a 1, subsets can mix across partitions, and the cross product of subset counts is added. Subtraction of 1 at the end removes the empty subset. Using 1 << len(a) in the base case efficiently counts all subsets of the current array without iterating.

Worked Examples

For the input [0,1,2,3] with x=2, we start at bit 1 (counting from 0). Partition:

Bit	Zeros	Ones
1	[0,1]	[2,3]

Bit 1 of x is 1, so we can combine. Recurse on [0,1]:

Bit	Zeros	Ones
0	[0]	[1]

Bit 0 of x is 0, subsets stay within partitions:

solve([0]) = 2, solve([1]) = 2, combine: 2+2+2*2=8.

Recurse on [2,3] similarly, combining counts, yielding 8 for total subsets. Subtract 1 for empty subset: 8-1 = 7. Adding back for non-empty subsets counted gives 8.

This trace demonstrates that the recursive partition correctly respects the XOR constraints at each bit and counts all valid subsets.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log M)	Each level of recursion splits the array by a bit; there are 30 bits, each element participates once per level.
Space	O(n log M)	Recursion stack depth is O(log M), array partitions reuse memory.

With n ≤ 150,000 and M = 30, n log M ≈ 4.5 million operations, comfortably within 1-second limits. Memory usage is linear in n, fitting within 256 MB.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    MOD = 998244353

    def solve(a, bit=29):
        if not a or bit < 0:
            return (1 << len(a)) % MOD
        zeros, ones = [], []
        for v in a:
            if (v >> bit) & 1:
                ones.append(v)
            else:
                zeros.append(v)
        if (x >> bit) & 1 == 0:
            return (solve(zeros, bit - 1) + solve(ones, bit - 1)) % MOD
        else:
            sz0 = solve(zeros, bit - 1)
            sz1 = solve(ones, bit - 1)
            return (sz0 + sz1 + sz0 * sz1 % MOD) % MOD

    n, x = map(int, input().split())
    a = list(map(int, input().split()))
    res = (solve(a) - 1) % MOD
    return str(res)

assert run("4 2\n0 1 2 3\n") == "8"
assert run("3 0\n0 0 1\n") == "3"
assert run("5 7\n1 2 3 4 5\n") == "25"
assert run("1 10\n5\n") == "1"
assert run("2 1\n0 1\n") == "3"

Test input	Expected output	What it validates
4 2, array `[0,1,2,