test/math/xorbasis.test.cpp

• View this file on GitHub
• Last update: 2025-10-17 11:51:02+08:00
• Problem: https://judge.yosupo.jp/problem/intersection_of_f2_vector_spaces

Depends on

• src/math/xorbasis.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/intersection_of_f2_vector_spaces
#include <bits/stdc++.h>
#define PUSHB push_back
#define ALL(a) (a).begin(), (a).end()
using namespace std;

#include "../../src/math/xorbasis.hpp"
constexpr int MAXLOG = 32;

void solve() {
  auto init = []() -> pair<XorBasis<MAXLOG>, int> {
    XorBasis<MAXLOG> xb;
    int n;
    cin >> n;
    for (int _ = 0; _ < n; _++) {
      int x;
      cin >> x;
      xb.insert(x);
    }
    return {xb, n};
  };
  auto [xb1, n] = init();
  auto [xb2, m] = init();
  auto xb3 = xb1 & xb2;
  vector<int> ans;
  for (const auto& v : xb3.data) {
    if (v.any()) ans.PUSHB(v.to_ulong());
  }
  cout << ans.size();
  for (int x : ans) cout << " " << x;
  cout << "\n";
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int tt = 1;
  cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}

#line 1 "test/math/xorbasis.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/intersection_of_f2_vector_spaces
#include <bits/stdc++.h>
#define PUSHB push_back
#define ALL(a) (a).begin(), (a).end()
using namespace std;

#line 1 "src/math/xorbasis.hpp"
// 插入元素时间复杂度 $\mathcal{O}(L)$. 基底各数字二进制最高位不同.
template <int L>
struct XorBasis {
  array<bitset<L>, L> data;
  bool insert(bitset<L> x) {
    for (int i = L - 1; i >= 0; i--) {
      if (!x[i]) continue;
      if (data[i].none()) return data[i] = x, true;
      x ^= data[i];
    }
    return false;
  }
  friend XorBasis operator&(XorBasis lhs, const XorBasis& rhs) {
    XorBasis ret;
    array<bitset<L>, L> buf{};
    for (int i = L - 1; i >= 0; i--) {
      auto x = rhs.data[i], y = x;
      for (int k = i; k >= 0 && x.any(); k--) {
        if (!x[k]) continue;
        if (lhs.data[k].none()) lhs.data[k] = x, buf[k] = y;
        x ^= lhs.data[k], y ^= buf[k];
      }
      ret.insert(y);
    }
    return ret;
  }
};
#line 8 "test/math/xorbasis.test.cpp"
constexpr int MAXLOG = 32;

void solve() {
  auto init = []() -> pair<XorBasis<MAXLOG>, int> {
    XorBasis<MAXLOG> xb;
    int n;
    cin >> n;
    for (int _ = 0; _ < n; _++) {
      int x;
      cin >> x;
      xb.insert(x);
    }
    return {xb, n};
  };
  auto [xb1, n] = init();
  auto [xb2, m] = init();
  auto xb3 = xb1 & xb2;
  vector<int> ans;
  for (const auto& v : xb3.data) {
    if (v.any()) ans.PUSHB(v.to_ulong());
  }
  cout << ans.size();
  for (int x : ans) cout << " " << x;
  cout << "\n";
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int tt = 1;
  cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	max_minus_1_random_00	AC	1136 ms	4 MB
g++	max_minus_1_random_01	AC	1132 ms	4 MB
g++	max_minus_1_random_02	AC	1132 ms	4 MB
g++	max_minus_1_random_03	AC	1134 ms	4 MB
g++	max_minus_1_random_04	AC	1135 ms	3 MB
g++	max_random_00	AC	1129 ms	4 MB
g++	max_random_01	AC	1224 ms	4 MB
g++	max_random_02	AC	1137 ms	4 MB
g++	max_random_03	AC	1153 ms	4 MB
g++	max_random_04	AC	1140 ms	4 MB
g++	nmk_all_00	AC	506 ms	4 MB
g++	random_00	AC	512 ms	4 MB
g++	random_01	AC	514 ms	4 MB
g++	random_02	AC	524 ms	4 MB
g++	random_03	AC	517 ms	4 MB
g++	random_04	AC	519 ms	4 MB

Back to top page