CP-Algorithms Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub cp-algorithms/cp-algorithms-aux

:heavy_check_mark: Inverse Matrix (Mod 2) (verify/data_structures/bitpack/inv_mod_2.test.cpp)

Depends on

Code

// @brief Inverse Matrix (Mod 2)
#define PROBLEM "https://judge.yosupo.jp/problem/inverse_matrix_mod_2"
#pragma GCC optimize("Ofast,unroll-loops")
#include "cp-algo/data_structures/bitpack.hpp"
#include <bits/stdc++.h>

using namespace std;
using namespace cp_algo::data_structures;

const int maxn = 1 << 13;
bitpack<maxn> a[maxn];

void solve() {
    int n;
    cin >> n;
    string row;
    vector<int> lead(n);
    for(int i = 0; i < n; i++) {
        cin >> row;
        a[i] = row;
        a[i].set(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] >= n) {
            cout << -1 << "\n";
            return;
        }
        for(int j = 0; j < i; j++) {
            if(a[j][lead[i]]) {
                a[j].xor_hint(a[i], lead[i]);
            }
        }
    }
    for(int i = 0; i < n; i++) {
        while(lead[i] != i) {
            swap(a[i], a[lead[i]]);
            swap(lead[i], lead[lead[i]]);
        }
        cout << a[i].to_string().substr(n, n) << "\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/data_structures/bitpack/inv_mod_2.test.cpp"
// @brief Inverse Matrix (Mod 2)
#define PROBLEM "https://judge.yosupo.jp/problem/inverse_matrix_mod_2"
#pragma GCC optimize("Ofast,unroll-loops")
#line 1 "cp-algo/data_structures/bitpack.hpp"



#include <cstdint>
#include <cstddef>
#include <string>
#include <array>
#include <bit>
namespace cp_algo::data_structures {
    template<size_t n, typename Int = uint64_t>
    struct bitpack {
        static constexpr uint8_t bits_per_block = 8 * sizeof(Int);
        static constexpr uint32_t blocks = (n + bits_per_block - 1) / bits_per_block;
        std::array<Int, blocks> data;

        auto operator <=> (bitpack const& t) const = default;

        bitpack(): data{} {}
        bitpack(std::string bits): data{} {
            size_t rem = size(bits) % bits_per_block;
            if(rem) {
                bits += std::string(bits_per_block - rem, '0');
            }
            for(size_t i = 0, pos = 0; pos < size(bits); i++, pos += bits_per_block) {
                for(size_t j = bits_per_block; 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 / bits_per_block; 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;
        }

        int operator[](size_t i) const {
            return (data[i / bits_per_block] >> (i % bits_per_block)) & 1;
        }
        void set(size_t i) {
            data[i / bits_per_block] |= 1ULL << (i % bits_per_block);
        }

        std::string to_string() const {
            std::string res(blocks * bits_per_block, '0');
            for(size_t i = 0, pos = 0; i < blocks; i++, pos += bits_per_block) {
                Int block = data[i];
                for(size_t j = 0; j < bits_per_block; 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 += bits_per_block;
                i++;
            }
            if(i < blocks) {
                res += std::countr_zero(data[i]);
            }
            return std::min(res, n);
        }
    };
}

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

using namespace std;
using namespace cp_algo::data_structures;

const int maxn = 1 << 13;
bitpack<maxn> a[maxn];

void solve() {
    int n;
    cin >> n;
    string row;
    vector<int> lead(n);
    for(int i = 0; i < n; i++) {
        cin >> row;
        a[i] = row;
        a[i].set(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] >= n) {
            cout << -1 << "\n";
            return;
        }
        for(int j = 0; j < i; j++) {
            if(a[j][lead[i]]) {
                a[j].xor_hint(a[i], lead[i]);
            }
        }
    }
    for(int i = 0; i < n; i++) {
        while(lead[i] != i) {
            swap(a[i], a[lead[i]]);
            swap(lead[i], lead[lead[i]]);
        }
        cout << a[i].to_string().substr(n, n) << "\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 :heavy_check_mark: AC 6 ms 12 MB
g++ example_01 :heavy_check_mark: AC 6 ms 12 MB
g++ example_02 :heavy_check_mark: AC 6 ms 12 MB
g++ lowrank_max_random_00 :heavy_check_mark: AC 6 ms 12 MB
g++ lowrank_max_random_01 :heavy_check_mark: AC 6 ms 12 MB
g++ lowrank_max_random_02 :heavy_check_mark: AC 6 ms 12 MB
g++ lowrank_max_random_03 :heavy_check_mark: AC 270 ms 12 MB
g++ lowrank_max_random_04 :heavy_check_mark: AC 276 ms 12 MB
g++ lowrank_max_random_05 :heavy_check_mark: AC 248 ms 12 MB
g++ lowrank_max_random_06 :heavy_check_mark: AC 83 ms 12 MB
g++ lowrank_max_random_07 :heavy_check_mark: AC 182 ms 12 MB
g++ max_fullrank_00 :heavy_check_mark: AC 307 ms 12 MB
g++ max_fullrank_01 :heavy_check_mark: AC 294 ms 12 MB
g++ max_fullrank_02 :heavy_check_mark: AC 305 ms 12 MB
g++ max_fullrank_03 :heavy_check_mark: AC 312 ms 12 MB
g++ max_random_00 :heavy_check_mark: AC 271 ms 12 MB
g++ max_random_01 :heavy_check_mark: AC 295 ms 12 MB
g++ max_random_02 :heavy_check_mark: AC 273 ms 12 MB
g++ max_random_03 :heavy_check_mark: AC 273 ms 12 MB
g++ perm_max_random_00 :heavy_check_mark: AC 6 ms 12 MB
g++ perm_max_random_01 :heavy_check_mark: AC 6 ms 12 MB
g++ random_00 :heavy_check_mark: AC 13 ms 12 MB
g++ random_01 :heavy_check_mark: AC 7 ms 12 MB
g++ random_02 :heavy_check_mark: AC 6 ms 12 MB
g++ random_03 :heavy_check_mark: AC 171 ms 12 MB
g++ random_fullrank_00 :heavy_check_mark: AC 16 ms 12 MB
g++ random_fullrank_01 :heavy_check_mark: AC 7 ms 12 MB
g++ random_fullrank_02 :heavy_check_mark: AC 6 ms 12 MB
g++ random_fullrank_03 :heavy_check_mark: AC 195 ms 12 MB
g++ small_random_00 :heavy_check_mark: AC 6 ms 12 MB
g++ small_random_01 :heavy_check_mark: AC 6 ms 12 MB
g++ small_random_02 :heavy_check_mark: AC 6 ms 12 MB
g++ small_random_03 :heavy_check_mark: AC 6 ms 12 MB
g++ small_random_04 :heavy_check_mark: AC 6 ms 12 MB
g++ small_random_05 :heavy_check_mark: AC 6 ms 12 MB
g++ small_random_06 :heavy_check_mark: AC 6 ms 12 MB
g++ small_random_07 :heavy_check_mark: AC 6 ms 12 MB
Back to top page