SUBSUB - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

XOR Basics

PROBLEM:

You’re given an array A and a parameter K.
Construct an array B that contains the XORs of all length-K subsequences of A.
Compute the number of distinct subsequence XORs of B.

EXPLANATION:

Solving this problem requires linear algebra knowledge: specifically, of the XOR basis and a couple of its properties in general.
If you’re unfamiliar with the concept, it is recommended to read through USACO Guide and/or this Codeforces blog (the comments are helpful too!) first.

Let’s try to solve a couple of specific cases first.

To begin, we start with K = 1.
Here, the array B is simply the array A itself.
So, we’re interested in just computing the number of distinct XORs that appear as subsequences of A.

This is a well-known problem, with the answer being 2^r, where r = \text{rank}(A) is the rank of the span of A; or in other words the size of its basis.
So, the K = 1 case can be solved quite easily by just building the XOR basis of A, which using the standard algorithm takes \mathcal{O}(N\cdot\log(\max(A))) time, easily fast enough here.

Next, let’s look at K = 2.
Here, B contains all pairwise XORs of A, and we want to know the XORs that can be obtained by choosing some of these pairwise XORs.

In terms of the original array A, observe that we can obtain exactly the XORs of any even-length subsequence of A.

  • To obtain the XOR of indices (i_1, i_2, \ldots, i_{2k}), we split it into (i_1, i_2), (i_3, i_4), \ldots, (i_{2k-1}, i_{2k}).
    Each of the k pairs has its XOR appear in B, so we can just take their XORs to obtain what we want.
  • On the other hand, it’s never possible to obtain an odd-length subsequence, for simple parity reasons.

So, here f(B) simply equals the number of distinct XORs formed by all the even-length subsequences of A.

This can also be computed using the XOR basis, with the help of a small trick.
Let’s create a new array A', such that A'_i = A_i \oplus 2^{30}.
(Recall that the input has A_i \lt 2^{30}, so this really just adds an additional bit to every element).

Now, observe that the XOR of any even-length subsequence will end up cancelling out the 2^{30} bit and hence be \lt 2^{30}, while the XOR of any odd-length subsequence will not cancel out the bit and hence be \ge 2^{30}.
So, even-length subsequences of A' will have the exact same XOR as the corresponding even-length subsequence of A, while odd-length subsequences of A' will have a XOR that doesn’t appear as the XOR of any subsequence of A.

Thus, we’re looking to count all elements in the span that are \lt 2^{30}.

This ends up being quite simple: the answer is simply 2^{r - 1}, where r = \text{rank}(A').
To understand why: consider building the basis of A' in REF. There will be exactly one element with the bit 2^{30} set; and so all XORs that include 2^{30} must have this basis element chosen.
So, the XORs that don’t include 2^{30} are simply all combinations of the other \text{rank}(A') - 1 basis elements.

Next, let’s look at K = 3.
Here, it turns out we don’t have to do anything new at all - after all, given triplets of elements, we can obtain any singleton!

To see why: suppose we want to obtain A_i as a XOR.
Choose any three other indices, say x, y, z.
Then, we have

(A_i \oplus A_x \oplus A_y) \oplus (A_i \oplus A_y \oplus A_z) \oplus (A_i \oplus A_x \oplus A_y) = A_i

i was an arbitrary index, so we’re able to obtain any singleton this way.
Thus, for K = 3, the answer is the same as the answer for K = 1.

In fact, this applies to every odd integer K as well: they all have the same answer as K = 1.

Applying similar logic to even K shows that they all have the same answer as K = 2; again any pair can be obtained but for parity reasons odd lengths are unreachable.

There is only one edge case: K = N.
Here, we don’t have enough freedom to combine different tuples to form singletons/pairs - because we only have the single element (A_1\oplus A_2\oplus\ldots\oplus A_N).

So, if (A_1\oplus A_2\oplus\ldots\oplus A_N) = 0 then the answer is 1 (only 0 is obtainable); otherwise the answer is 2 since we can obtain both 0 and one non-zero value.

Putting it all together:

  • If K = N, the answer is either 1 or 2, depending on the XOR-sum of A being 0 or not.
  • If K \lt N and K is odd, the answer is 2^{\text{rank}(A)}.
  • If K \lt N and K is even, the answer is 2^{\text{rank}(A')-1}, where A' is obtained as A'_i = A_i\oplus 2^{30}.

TIME COMPLEXITY:

\mathcal{O}(N\cdot \log(\max(A))) per testcase.

CODE:

Editorialist's code (C++) 
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

template<typename T>
struct Basis {
    static const int SZ = 32;
    array<T, SZ> basis{};
    Basis() {}
    int Rank() {
        int rank = 0;
        for (auto x : basis)
            rank += (x > 0);
        return rank;
    }
    void Add(T x) {
        for (auto &y : basis) {
            if (y) x = min(x, x ^ y);
            else { y = x; x = 0; }
            if (!x) break;
        }
    }
};

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    int t; cin >> t;
    while (t--) {
        int n, k; cin >> n >> k;
        vector a(n, 0);
        for (int &x : a) cin >> x;

        if (n == k) {
            int tot = 0;
            for (int x : a) tot ^= x;
            if (tot == 0) cout << 1 << '\n';
            else cout << 2 << '\n';
            continue;
        }

        if (k%2 == 0) {
            for (int &x : a) x |= 1 << 30;
        }
        Basis<int> B;
        for (int x : a) B.Add(x);

        cout << (1 << (B.Rank() - (k%2 == 0))) << '\n';
    }
}
3 Likes