Mad Scientist's Problem (Editorial)

Lets for every a_i find the minimal number we can change it to when using our operations. Let this function be $f(x)$. It is not hard to see that we can make a_i equal a_j if and only if f(a_i)=f(a_j). The proof is left as exercise to the reader.

Then we reduced our problem to finding the number of unique elements of an array f(a_i). For that, we need to learn how to calculate $f(x)$ efficiently. To do that, we can construct XOR basis of the set $b$ and using its properties we can easily find $f(x)$. In XOR basis, every element is "responsible" for some bit (in usually constructed basis, the element is "responsible" for the highest bit it has). In the basis, there are no two numbers with the same highest bit, so that's what "responsible" is standing for. Using this property we can see that finding $f(x)$ is the same procedure as adding a new number to basis, but if we found a new element to extend the basis (that is f(x) \neq 0) we just don't add it.

Complexity: O(n \cdot \log{max_a}).

You can learn more about XOR basis by the link.

#include <bits/stdc++.h>

using namespace std;

struct Basis {
    vector<int> basis;
    int reduce(int x) {
        for (int b : basis) {
            x = min(x, x ^ b);
        }
        return x;
    }
    void add(int x) {
        x = reduce(x);
        if (x > 0) {
            basis.push_back(x);
        }
    }
};
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }
    Basis basis;
    for (int i = 0; i < m; i++) {
        basis.add(b[i]);
    }
    set<int> st;
    for (int i = 0; i < n; i++) {
        st.insert(basis.reduce(a[i]));
    }
    cout << st.size() << "\n";
}