Auto comment: topic has been updated by Sammmmmmm (previous revision, new revision, compare).

where is this problem found??? or is it just a problem you created by urself?

This problem can be solvable with trie.

I like this problem, it has clever trick I've not seen exactly in this form. Assume numbers are < 2^30. The key is noticing that if (a[i] & a[j]) == 0 then at least one of the numbers in a valid pair must have bitcount less <= 15. Also, 30C15 ~ 1e8.

Let's split numbers into two groups, those with bitcount <= 15 in set S and those >= 15 in set T. Then from before, no pairs between elements in T will work, so we only need to count pairs in S and pairs between S and T.

For pairs in S, we are going to consider for each element in S how many other pairs in S intersect with its bitmask and subtract those. To find number of masks that intersect another mask we can use SOS dp.

For pairs between S and T, we are going to consider for each element in T how many elements are there in S only using bits in unset bits of T element. We can find number of elements within mask using SOS dp as well.

Now you may say SOS dp is too slow because it is 30 * 2^30. However, realize in both cases described above we are only iterating over masks with at most 15 bits. This means SOS dp will actually be more like 30 * 30C15 :eyes:. With a bit of constant optimization and luck something along this line will hopefully pass.

Actually I'm not confident this is right approach, it seems it will be difficult to deal with memory, if there is way better solution someone please let me know :pray:.

Just deleted my comment related to code,

I misunderstood the constraints earlier_

this is from ongoing contest

by the way，i want to ask how to solve ai & aj = k problem. may be sqrt，but i do not know how.

Brute force in custom invocation (c++20) on codeforces only costs 546ms.

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
constexpr int m = 32;
int f(int *a, int *b) {
  int res = 0;
  for (int i = 0; i < m; i += 1) {
    for (int j = 0; j < m; j += 1) {
      res += (a[i] & b[j]) == 0;
    }
  }
  return res;
}
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n = 100000;
  vector<int> a(n);
  mt19937_64 mt;
  uniform_int_distribution uid(0, 1000000000);
  for (int &ai : a) {
    ai = uid(mt);
  }
  // int check = 0;
  // for (int i = 0; i < n; i += 1) {
  //   for (int j = i + 1; j < n; j += 1) {
  //     check += (a[i] & a[j]) == 0;
  //   }
  // }
  // cout << check << "\n";
  int ans = 0;
  for (int i = 0; i < n; i += m) {
    for (int j = i + m; j < n; j += m) {
      ans += f(a.data() + i, a.data() + j);
    }
  }
  for (int i = 0; i < n; i += m) {
    for (int j = 0; j < m; j += 1) {
      for (int k = j + 1; k < m; k += 1) {
        ans += (a[i + j] & a[i + k]) == 0;
      }
    }
  }
  cout << ans << "\n";
}