Bitwise AND Partition Counting: Analysis and Algorithm Implementation

Problem Statement

Given (n) integers (a_1, a_2, \dots, a_n), randomly partition them into two non-empty groups. Calculate the number of partitions where the bitwise AND of the numbers in each group results in the same value.

Constraints: (1 \le n \le 60), (0 \le a_i < 2^{17}).

Key Analysis

Let (x) and (y) be the bitwise AND results of the two groups. For a valid partition, (x = y). Define (S = a_1 & a_2 & \dots & a_n). For any valid partition, (x = y = S).

Therefore, the number of valid partitions equals the total number of partitions minus the number of invalid partitions. The total number of non-empty partitions is (2^n - 2).

Observing the bits of (S):

• Bits where (S) is 1 must be 1 in every (a_i). These bits do not affect partition validity.
• Bits where (S) is 0: For a partition to be invalid regarding a specific bit position, all numbers in one group must have that bit as 1, causing the group's AND result to be 1 at that position, differing from (S)'s 0.

Thus, an invalid partition requires that for at least one bit position (b) where (S_b = 0), all numbers assigned to one group have (b = 1).

Solution via Inclusion-Exclusion

Let (m) be the number of bit positions under consideration where (S_b = 0). There are 17 bits total. Define a bitmask (i) (where (0 \le i < 2^{17})) representing a set of bits. For partition validity, no bit in (i) should cause invalidity.

Apply the inclusion-exclusion principle over all bitmasks (i): [ \text{Valid} = \sum_{i} (-1)^{|i|} \cdot f(i) ] where (|i|) is the number of bits set in (i), and (f(i)) is the number of partitions that are "valid" when considering the bits in (i) as potentially causing invalidity. More precisely, (f(i)) counts partitions where, for every bit (b) set in (i), not all numbers with (b=0) are in the same group? Wait, let's refine.

Actually, for a given mask (i), we enforce that for each bit (b) in (i), all numbers where (a_j) has bit (b = 0) must be placed in the same group (to potentially create an invalid condition for that bit). This creates constraints that merge these numbers into connected components via a DSU (Disjoint Set Union). After processing all bits in (i), suppose we have (\text{comp}) components. The number of ways to assign these components to two groups (with both groups non-empty) is (2^{\text{comp}} - 2). This counts partitions that satisfy the "all zero together" constraint for each bit in (i).

By inclusion-exclusion, summing ((-1)^{|i|} (2^{\text{comp}} - 2)) over all masks (i) yields the count of partitions where no bit causes invalidity, i.e., valid partitions.

Algorithm Steps

1. Compute (S = a_1 & a_2 & \dots & a_n).
2. Iterate over all bitmasks (i) from 0 to (2^{17}-1). Skip masks where (i) has any bit set that is also set in (S) (since those bits are always 1 and cannot cause invalidity).
3. For each mask (i):
   • Initialize DSU with each element as its own set.
   • For each bit position (b) set in (i):
     • Identify all indices (j) where bit (b) of (a_j) is 0.
     • Merge these indices into one DSU component.
   • Let (\text{cnt}) be the number of DSU components after processing.
   • Contribution: ((-1)^{\text{popcount}(i)} \cdot (2^{\text{cnt}} - 2)).
4. Sum all contributions to get the final answer.

Complexity: (O(2^{17} \cdot n \cdot \alpha(n))), feasible within constraints.

Implementation

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 65;
const int MAX_BITS = 17;
const int FULL_MASK = (1 << MAX_BITS);

int parent[MAX_N];

int find_set(int v) {
    if (v == parent[v]) return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) parent[b] = a;
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    int common_and = (1 << MAX_BITS) - 1;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        common_and &= arr[i];
    }

    long long answer = 0;
    for (int mask = 0; mask < FULL_MASK; ++mask) {
        if (mask & common_and) continue;
        
        iota(parent, parent + n, 0);
        int components = n;
        
        for (int bit = 0; bit < MAX_BITS; ++bit) {
            if (!(mask & (1 << bit))) continue;
            
            int first_zero_idx = -1;
            for (int i = 0; i < n; ++i) {
                if (!(arr[i] & (1 << bit))) {
                    if (first_zero_idx == -1) {
                        first_zero_idx = i;
                    } else {
                        int root_a = find_set(first_zero_idx);
                        int root_b = find_set(i);
                        if (root_a != root_b) {
                            union_sets(root_a, root_b);
                            components--;
                        }
                    }
                }
            }
        }
        
        long long ways = (1LL << components) - 2;
        if (__builtin_popcount(mask) % 2 == 1) {
            answer -= ways;
        } else {
            answer += ways;
        }
    }
    cout << answer << endl;
    return 0;
}

Sliding Window with Maximum-Minimum Ratio

Problem Statement

Givan an array (a) of length (n), and integers (m, L, R), find the maximum value of: [ \frac{\text{Max}(l, r) - \text{Min}(l, r)}{r - l + m} ] over all subarrays ([l, r]) satisfying (L \le r - l + 1 \le R).

Here, (\text{Max}(l, r)) and (\text{Min}(l, r)) denote the maximum and minimum in the subarray.

Optimization Approach

We aim to maximize (\frac{\text{Max} - \text{Min}}{\text{len} + m}) where (\text{len} = r - l + 1).

Observation: For a subarray achieving the maximum ratio, its endpoints must be the maximum and minimum elements with in that window, unless the window length is forced by (L) or (R).

Use binary search on the answer (x). We need to check if there exists a subarray of length between (L) and (R) such that: [ \frac{\text{Max} - \text{Min}}{\text{len} + m} \ge x ] Rearranging: [ \text{Max} - \text{Min} \ge x \cdot (\text{len} + m) ] [ \text{Max} - \text{Min} \ge x \cdot (r - l + 1 + m) ] [ \text{Max} - \text{Min} + x \cdot l - x \cdot r \ge x \cdot m ]

Assume without loss of generality that (a_l \le a_r) (the other case can be handled by reversing the array and repeating). Then (\text{Max} - \text{Min} = a_r - a_l). The inequality becomes: [ a_r - a_l + x \cdot l - x \cdot r \ge x \cdot m ] [ (a_r - x \cdot r) - (a_l - x \cdot l) \ge x \cdot m ] Define (b_i = a_i - x \cdot i). We need to find indices (l, r) with (L \le r - l + 1 \le R) such that (b_r - b_l \ge x \cdot m).

This can be checked using a sliding window with a deque to maintain the minimum (b_l) for valid start indices.

Algorithm Steps for Checking a Given (x)

1. Compute array (b) where (b_i = a_i - x \cdot i).
2. Initialize a deque min_q to store candidate start indices.
3. For each end index (r) from (L) to (n):
   • While min_q is not empty and (b[\text{back}] \ge b[r - L + 1]) (using 1-based indexing for clarity), pop the back.
   • Push (r - L + 1) onto min_q.
   • While the front index is less than (r - R + 1), pop the front.
   • If (b[r] - b[\text{front}] \ge x \cdot m), return true.
4. Return false if no such pair is found.

Additionally, we need to handle the case where the maximum is at the left end and minimum at the right end. This can be done by running the same algorithm on the reversed array.

Implementation

#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-7;

bool check(const vector<int>& a, int m, int L, int R, double x) {
    int n = a.size();
    vector<double> b(n + 1);
    for (int i = 1; i <= n; ++i) {
        b[i] = a[i - 1] - x * i;
    }
    deque<int> dq;
    for (int r = L; r <= n; ++r) {
        int candidate = r - L + 1;
        while (!dq.empty() && b[dq.back()] >= b[candidate]) {
            dq.pop_back();
        }
        dq.push_back(candidate);
        while (!dq.empty() && dq.front() < r - R + 1) {
            dq.pop_front();
        }
        if (!dq.empty() && b[r] - b[dq.front()] >= x * m) {
            return true;
        }
    }
    return false;
}

double solve(const vector<int>& a, int m, int L, int R) {
    double low = 0.0, high = 2e9;
    for (int iter = 0; iter < 60; ++iter) {
        double mid = (low + high) / 2;
        if (check(a, m, L, R, mid) || check(vector<int>(a.rbegin(), a.rend()), m, L, R, mid)) {
            low = mid;
        } else {
            high = mid;
        }
    }
    return low;
}

int main() {
    int n, m, L, R;
    cin >> n >> m >> L >> R;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    double ans = solve(a, m, L, R);
    cout << fixed << setprecision(4) << ans << endl;
    return 0;
}