This documentation is automatically generated by competitive-verifier/competitive-verifier
// @brief Matrix Product (Mod 2)
#define PROBLEM "https://judge.yosupo.jp/problem/matrix_product_mod_2"
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("tune=native")
#include "cp-algo/data_structures/bitpack.hpp"
#include <bits/stdc++.h>
using namespace std;
using cp_algo::data_structures::bitpack;
const int maxn = 1 << 12;
bitpack<maxn> a[maxn], b[maxn], c[maxn];
void solve() {
int n, m, k;
cin >> n >> m >> k;
string row;
for(int i = 0; i < n; i++) {
cin >> row;
a[i] = row;
}
for(int i = 0; i < m; i++) {
cin >> row;
b[i] = row;
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(a[i][j]) {
c[i] ^= b[j];
}
}
}
for(int i = 0; i < n; i++) {
row = c[i].to_string().substr(0, k);
cout << row << "\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/prod_mod_2.test.cpp"
// @brief Matrix Product (Mod 2)
#define PROBLEM "https://judge.yosupo.jp/problem/matrix_product_mod_2"
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("tune=native")
#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 7 "verify/data_structures/bitpack/prod_mod_2.test.cpp"
#include <bits/stdc++.h>
using namespace std;
using cp_algo::data_structures::bitpack;
const int maxn = 1 << 12;
bitpack<maxn> a[maxn], b[maxn], c[maxn];
void solve() {
int n, m, k;
cin >> n >> m >> k;
string row;
for(int i = 0; i < n; i++) {
cin >> row;
a[i] = row;
}
for(int i = 0; i < m; i++) {
cin >> row;
b[i] = row;
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(a[i][j]) {
c[i] ^= b[j];
}
}
}
for(int i = 0; i < n; i++) {
row = c[i].to_string().substr(0, k);
cout << row << "\n";
}
}
signed main() {
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
while(t--) {
solve();
}
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | example_00 | AC | 6 ms | 10 MB |
g++ | example_01 | AC | 5 ms | 10 MB |
g++ | example_02 | AC | 5 ms | 10 MB |
g++ | many_1_00 | AC | 202 ms | 10 MB |
g++ | many_1_01 | AC | 187 ms | 10 MB |
g++ | max_random_00 | AC | 206 ms | 10 MB |
g++ | max_random_01 | AC | 200 ms | 10 MB |
g++ | max_random_02 | AC | 210 ms | 10 MB |
g++ | middle_00 | AC | 10 ms | 10 MB |
g++ | middle_01 | AC | 6 ms | 10 MB |
g++ | middle_02 | AC | 6 ms | 10 MB |
g++ | middle_03 | AC | 6 ms | 10 MB |
g++ | middle_04 | AC | 10 ms | 10 MB |
g++ | random_00 | AC | 115 ms | 10 MB |
g++ | random_01 | AC | 96 ms | 10 MB |
g++ | random_02 | AC | 90 ms | 10 MB |
g++ | small_00 | AC | 6 ms | 10 MB |
g++ | small_01 | AC | 6 ms | 10 MB |
g++ | small_02 | AC | 6 ms | 10 MB |
g++ | small_03 | AC | 6 ms | 10 MB |
g++ | small_04 | AC | 6 ms | 10 MB |
g++ | small_05 | AC | 6 ms | 10 MB |
g++ | small_06 | AC | 6 ms | 10 MB |
g++ | small_07 | AC | 6 ms | 10 MB |
g++ | small_08 | AC | 6 ms | 10 MB |
g++ | small_09 | AC | 6 ms | 10 MB |