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

• View this file on GitHub
• Last update: 2024-05-03 13:54:12+09:00
• Include: #include "linear_algebra_matrix/f2_linear_space.hpp"

$\mathbb{F}_{2}$ 線形空間に関する各種演算．

使用方法

A の元で張られる線形空間と B の元で張られる線形空間の共通部分の基底を一つ求める関数方法．

int n, m;
vector<int> A(n), B(m);

vector<int> C = f2_intersection(A, B);

問題例

• Library Checker: Intersection of F_2 vector spaces

Verified with

• linear_algebra_matrix/test/f2_intersection.test.cpp

Code

#pragma once
#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 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;
}

Back to top page