System of Linear Equations (Mod 2) (verify/structures/bitpack/system_mod_2.test.cpp)

View this file on GitHub
Last update: 2024-11-15 00:01:35+01:00
Problem: https://judge.yosupo.jp/problem/system_of_linear_equations_mod_2

Depends on

Code

// @brief System of Linear Equations (Mod 2)
#define PROBLEM "https://judge.yosupo.jp/problem/system_of_linear_equations_mod_2"
#pragma GCC optimize("Ofast,unroll-loops")
#include "cp-algo/structures/bitpack.hpp"
#include <bits/stdc++.h>

using namespace std;
using cp_algo::structures::bitpack;

const int maxn = (1 << 12) + 1;
bitpack<maxn> a[maxn];

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> As(n);
    for(int i = 0; i < n; i++) {
        cin >> As[i];
    }
    string bs;
    cin >> bs;
    for(int i = 0; i < n; i++) {
        As[i] += bs[i];
        a[i] = As[i];
    }
    vector<int> lead(n);
    auto vars = views::iota(0, m + 1);
    set<int> free(begin(vars), end(vars));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < i; j++) {
            if(a[i][lead[j]]) {
                a[i].xor_hint(a[j], lead[j]);
            }
        }
        lead[i] = a[i].ctz();
        if(lead[i] == m) {
            cout << -1 << "\n";
            return;
        }
        if(lead[i] > m) {
            continue;
        }
        free.erase(lead[i]);
        for(int j = 0; j < i; j++) {
            if(a[j][lead[i]]) {
                a[j].xor_hint(a[i], lead[i]);
            }
        }
    }
    bitpack<maxn> x[maxn];
    for(auto [j, pj]: views::enumerate(free)) {
        x[j].set(pj);
        for(int i = 0; i < n; i++) {
            if(lead[i] < m && a[i][pj]) {
                x[j].set(lead[i]);
            }
        }
    }
    int rk = size(free) - 1;
    swap(x[0], x[rk]);
    cout << rk << "\n";
    for(int i = 0; i <= rk; i++) {
        cout << x[i].to_string().substr(0, m) << "\n";
    }
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    while(t--) {
        solve();
    }
}

#line 1 "verify/structures/bitpack/system_mod_2.test.cpp"
// @brief System of Linear Equations (Mod 2)
#define PROBLEM "https://judge.yosupo.jp/problem/system_of_linear_equations_mod_2"
#pragma GCC optimize("Ofast,unroll-loops")
#line 1 "cp-algo/structures/bitpack.hpp"



#line 1 "cp-algo/structures/bit_array.hpp"


#line 1 "cp-algo/util/bit.hpp"


#include <immintrin.h>
#include <cstdint>
#include <array>
#include <bit>
namespace cp_algo {
    template<typename Uint>
    constexpr size_t bit_width = sizeof(Uint) * 8;

    size_t order_of_bit(auto x, size_t k) {
        return k ? std::popcount(x << (bit_width<decltype(x)> - k)) : 0;
    }
    [[gnu::target("bmi2")]]
    size_t kth_set_bit(uint64_t x, size_t k) {
        return std::countr_zero(_pdep_u64(1ULL << k, x));
    }
    template<int fl = 0>
    void with_bit_floor(size_t n, auto &&callback) {
        if constexpr (fl >= 63) {
            return;
        } else if (n >> (fl + 1)) {
            with_bit_floor<fl + 1>(n, callback);
        } else {
            callback.template operator()<1ULL << fl>();
        }
    }
}

#line 4 "cp-algo/structures/bit_array.hpp"
namespace cp_algo::structures {
    template<size_t N, typename Uint = uint64_t>
    struct bit_array {
        static constexpr size_t width = bit_width<Uint>;
        static constexpr size_t blocks = N / width + 1;
        std::array<Uint, blocks> data = {};

        uint64_t word(size_t x) const {
            return data[x];
        }
        void set(size_t x) {
            data[x / width] |= 1ULL << (x % width);
        }
        void flip(size_t x) {
            data[x / width] ^= 1ULL << (x % width);
        }
        bool test(size_t x) const {
            return (data[x / width] >> (x % width)) & 1;
        }
        bool operator[](size_t x) const {
            return test(x);
        }
    };
}

#line 6 "cp-algo/structures/bitpack.hpp"
#include <cstddef>
#include <string>
#line 9 "cp-algo/structures/bitpack.hpp"
namespace cp_algo::structures {
    template<size_t n, typename Int = uint64_t>
    struct bitpack: bit_array<n, Int> {
        using Base = bit_array<n, Int>;
        using Base::width, Base::blocks, Base::data;
        auto operator <=> (bitpack const& t) const = default;

        bitpack() {}
        bitpack(std::string bits) {
            size_t rem = size(bits) % width;
            if(rem) {
                bits += std::string(width - rem, '0');
            }
            for(size_t i = 0, pos = 0; pos < size(bits); i++, pos += width) {
                for(size_t j = width; j; j--) {
                    data[i] *= 2;
                    data[i] ^= bits[pos + j - 1] == '1';
                }
            }
        }

        bitpack& xor_hint(bitpack const& t, size_t hint) {
            for(size_t i = hint / width; i < blocks; i++) {
                data[i] ^= t.data[i];
            }
            return *this;
        }
        bitpack& operator ^= (bitpack const& t) {
            return xor_hint(t, 0);
        }
        bitpack operator ^ (bitpack const& t) const {
            return bitpack(*this) ^= t;
        }

        std::string to_string() const {
            std::string res(blocks * width, '0');
            for(size_t i = 0, pos = 0; i < blocks; i++, pos += width) {
                Int block = data[i];
                for(size_t j = 0; j < width; j++) {
                    res[pos + j] = '0' + block % 2;
                    block /= 2;
                }
            }
            res.resize(n);
            return res;
        }

        size_t ctz() const {
            size_t res = 0;
            size_t i = 0;
            while(i < blocks && data[i] == 0) {
                res += width;
                i++;
            }
            if(i < blocks) {
                res += std::countr_zero(data[i]);
            }
            return std::min(res, n);
        }
    };
}

#line 5 "verify/structures/bitpack/system_mod_2.test.cpp"
#include <bits/stdc++.h>

using namespace std;
using cp_algo::structures::bitpack;

const int maxn = (1 << 12) + 1;
bitpack<maxn> a[maxn];

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> As(n);
    for(int i = 0; i < n; i++) {
        cin >> As[i];
    }
    string bs;
    cin >> bs;
    for(int i = 0; i < n; i++) {
        As[i] += bs[i];
        a[i] = As[i];
    }
    vector<int> lead(n);
    auto vars = views::iota(0, m + 1);
    set<int> free(begin(vars), end(vars));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < i; j++) {
            if(a[i][lead[j]]) {
                a[i].xor_hint(a[j], lead[j]);
            }
        }
        lead[i] = a[i].ctz();
        if(lead[i] == m) {
            cout << -1 << "\n";
            return;
        }
        if(lead[i] > m) {
            continue;
        }
        free.erase(lead[i]);
        for(int j = 0; j < i; j++) {
            if(a[j][lead[i]]) {
                a[j].xor_hint(a[i], lead[i]);
            }
        }
    }
    bitpack<maxn> x[maxn];
    for(auto [j, pj]: views::enumerate(free)) {
        x[j].set(pj);
        for(int i = 0; i < n; i++) {
            if(lead[i] < m && a[i][pj]) {
                x[j].set(lead[i]);
            }
        }
    }
    int rk = size(free) - 1;
    swap(x[0], x[rk]);
    cout << rk << "\n";
    for(int i = 0; i <= rk; i++) {
        cout << x[i].to_string().substr(0, m) << "\n";
    }
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    while(t--) {
        solve();
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	8 ms	8 MB
g++	example_01	AC	7 ms	8 MB
g++	example_02	AC	7 ms	8 MB
g++	max_lowrank_00	AC	79 ms	43 MB
g++	max_lowrank_01	AC	46 ms	43 MB
g++	max_lowrank_02	AC	84 ms	43 MB
g++	max_lowrank_03	AC	56 ms	43 MB
g++	max_lowrank_04	AC	202 ms	43 MB
g++	max_lowrank_05	AC	46 ms	43 MB
g++	max_lowrank_06	AC	77 ms	43 MB
g++	max_lowrank_07	AC	46 ms	43 MB
g++	max_lowrank_08	AC	162 ms	43 MB
g++	max_lowrank_09	AC	193 ms	43 MB
g++	max_random_00	AC	200 ms	43 MB
g++	max_random_01	AC	201 ms	43 MB
g++	max_random_02	AC	201 ms	43 MB
g++	max_random_03	AC	201 ms	43 MB
g++	max_random_04	AC	200 ms	43 MB
g++	max_small_00	AC	14 ms	8 MB
g++	max_small_01	AC	8 ms	8 MB
g++	random_00	AC	18 ms	9 MB
g++	random_01	AC	27 ms	9 MB
g++	random_02	AC	14 ms	8 MB
g++	random_03	AC	34 ms	16 MB
g++	random_04	AC	20 ms	12 MB
g++	small_max_00	AC	35 ms	8 MB
g++	small_max_01	AC	8 ms	8 MB
g++	small_random_00	AC	7 ms	8 MB
g++	small_random_01	AC	7 ms	8 MB
g++	small_random_02	AC	7 ms	8 MB
g++	small_random_03	AC	7 ms	8 MB
g++	small_random_04	AC	7 ms	8 MB
g++	smallest_00	AC	7 ms	8 MB
g++	smallest_01	AC	7 ms	8 MB
g++	smallest_02	AC	7 ms	8 MB
g++	smallest_03	AC	7 ms	8 MB