linear_algebra_matrix/test/f2_intersection.test.cpp

• View this file on GitHub
• Last update: 2024-05-03 14:04:55+09:00
• Problem: https://judge.yosupo.jp/problem/intersection_of_f2_vector_spaces

Depends on

• $\mathbb{F}_{2}$ linear space ($\mathbb{F}_{2}$ 線形空間) (linear_algebra_matrix/f2_linear_space.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/intersection_of_f2_vector_spaces"
#include "../f2_linear_space.hpp"

#include <iostream>
using namespace std;

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

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;
        vector<int> A(n);
        for (int &x : A) cin >> x;

        int m;
        cin >> m;
        vector<int> B(m);
        for (int &x : B) cin >> x;

        auto C = f2_intersection(A, B);

        cout << C.size();
        for (int x : C) cout << ' ' << x;
        cout << '\n';
    }
}

#line 1 "linear_algebra_matrix/test/f2_intersection.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/intersection_of_f2_vector_spaces"
#line 2 "linear_algebra_matrix/f2_linear_space.hpp"
#include <algorithm>
#include <utility>
#include <vector>

template <class Int> struct f2_vector_space {
    std::vector<Int> basis;

    f2_vector_space() = default;

    Int add(Int x) {
        for (const Int &b : basis) x = std::min(x, x ^ b);

        if (x) {
            basis.push_back(x);
            return x;
        } else {
            return Int(0);
        }
    }
};

std::vector<int> f2_intersection(const std::vector<int> &A, const std::vector<int> &B) {
    f2_vector_space<long long> tmp;
    for (int a : A) tmp.add(((long long)a << 32) + a);

    std::vector<int> ret;

    for (int b : B) {
        long long v = (long long)b << 32;

        auto u = tmp.add(v);
        if (u < (1LL << 32)) ret.push_back(u);
    }

    return ret;
}
#line 3 "linear_algebra_matrix/test/f2_intersection.test.cpp"

#include <iostream>
using namespace std;

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

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;
        vector<int> A(n);
        for (int &x : A) cin >> x;

        int m;
        cin >> m;
        vector<int> B(m);
        for (int &x : B) cin >> x;

        auto C = f2_intersection(A, B);

        cout << C.size();
        for (int x : C) cout << ' ' << x;
        cout << '\n';
    }
}

Back to top page