cp-library
競技プログラミング用 C++ ライブラリ
test/dynamic_bitset_matrix_product.test.cpp
test/dynamic_bitset_matrix_product.test.cpp · GitHub で見る
依存ライブラリ
コード
#define PROBLEM "https://judge.yosupo.jp/problem/matrix_product_mod_2"
#include "../data_structure/dynamic_bitset.hpp"
#include "../components/fast_io.hpp"
int main() {
FastInput in;
FastOutput out;
int n = 0, m = 0, k = 0;
in.read(n); in.read(m); in.read(k);
std::vector<DynamicBitset> rows;
rows.reserve(n);
for (int i = 0; i < n; ++i) rows.emplace_back(in.token());
std::vector<DynamicBitset> columns(k, DynamicBitset(m));
for (int i = 0; i < m; ++i) {
auto row = in.token();
for (int j = 0; j < k; ++j) if (row[j] == '1') columns[j].set(m - 1 - i);
}
std::string row(k, '0');
for (const auto &bits : rows) {
for (int j = 0; j < k; ++j) row[j] = char('0' + bits.intersection_parity(columns[j]));
out.println(row);
}
}
#line 1 "test/dynamic_bitset_matrix_product.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/matrix_product_mod_2"
#line 1 "data_structure/dynamic_bitset.hpp"
#line 1 "components/bitset_ops.hpp"
#include <bit>
#include <cstddef>
#include <cstdint>
#if defined(__x86_64__) && (defined(__GNUC__) || defined(__clang__))
#include <immintrin.h>
#endif
namespace bitset_ops_detail {
enum class Operation { identity, bit_and, bit_or, bit_xor, and_not };
template <Operation Op> inline std::uint64_t combine(std::uint64_t a, std::uint64_t b) {
if constexpr (Op == Operation::identity) return a;
if constexpr (Op == Operation::bit_and) return a & b;
if constexpr (Op == Operation::bit_or) return a | b;
if constexpr (Op == Operation::bit_xor) return a ^ b;
if constexpr (Op == Operation::and_not) return a & ~b;
}
template <Operation Op> inline std::size_t scalar(const std::uint64_t *a, const std::uint64_t *b, std::size_t n) {
std::size_t result = 0;
for (std::size_t i = 0; i < n; ++i) {
if constexpr (Op == Operation::identity) result += std::popcount(a[i]);
else result += std::popcount(combine<Op>(a[i], b[i]));
}
return result;
}
template <Operation Op>
#if defined(__GNUC__) && !defined(__clang__)
__attribute__((optimize("O3")))
#endif
inline std::size_t scalar_large(const std::uint64_t *a, const std::uint64_t *b, std::size_t n) {
return scalar<Op>(a, b, n);
}
#if defined(__x86_64__) && (defined(__GNUC__) || defined(__clang__))
template <Operation Op> __attribute__((target("avx512f,avx512vpopcntdq")))
inline std::size_t avx512(const std::uint64_t *a, const std::uint64_t *b, std::size_t n) {
__m512i sum = _mm512_setzero_si512();
std::size_t i = 0;
for (; n - i >= 8; i += 8) {
__m512i x = _mm512_loadu_si512(a + i);
if constexpr (Op != Operation::identity) {
__m512i y = _mm512_loadu_si512(b + i);
if constexpr (Op == Operation::bit_and) x = _mm512_and_si512(x, y);
if constexpr (Op == Operation::bit_or) x = _mm512_or_si512(x, y);
if constexpr (Op == Operation::bit_xor) x = _mm512_xor_si512(x, y);
if constexpr (Op == Operation::and_not) x = _mm512_andnot_si512(y, x);
}
sum = _mm512_add_epi64(sum, _mm512_popcnt_epi64(x));
}
return std::size_t(_mm512_reduce_add_epi64(sum)) + scalar<Op>(a + i, b ? b + i : nullptr, n - i);
}
template <Operation Op> __attribute__((target("avx2")))
inline std::size_t avx2(const std::uint64_t *a, const std::uint64_t *b, std::size_t n) {
const __m256i lookup = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
const __m256i mask = _mm256_set1_epi8(15), zero = _mm256_setzero_si256();
__m256i sum = zero;
std::size_t i = 0;
for (; n - i >= 4; i += 4) {
__m256i x = _mm256_loadu_si256(reinterpret_cast<const __m256i *>(a + i));
if constexpr (Op != Operation::identity) {
__m256i y = _mm256_loadu_si256(reinterpret_cast<const __m256i *>(b + i));
if constexpr (Op == Operation::bit_and) x = _mm256_and_si256(x, y);
if constexpr (Op == Operation::bit_or) x = _mm256_or_si256(x, y);
if constexpr (Op == Operation::bit_xor) x = _mm256_xor_si256(x, y);
if constexpr (Op == Operation::and_not) x = _mm256_andnot_si256(y, x);
}
__m256i low = _mm256_shuffle_epi8(lookup, _mm256_and_si256(x, mask));
__m256i high = _mm256_shuffle_epi8(lookup, _mm256_and_si256(_mm256_srli_epi16(x, 4), mask));
sum = _mm256_add_epi64(sum, _mm256_sad_epu8(_mm256_add_epi8(low, high), zero));
}
alignas(32) std::uint64_t lanes[4];
_mm256_store_si256(reinterpret_cast<__m256i *>(lanes), sum);
return std::size_t(lanes[0] + lanes[1] + lanes[2] + lanes[3]) + scalar<Op>(a + i, b ? b + i : nullptr, n - i);
}
inline bool has_avx512() {
static const bool enabled = __builtin_cpu_supports("avx512f") && __builtin_cpu_supports("avx512vpopcntdq");
return enabled;
}
inline bool has_avx2() {
static const bool enabled = __builtin_cpu_supports("avx2");
return enabled;
}
#endif
template <Operation Op>
#if defined(__GNUC__) && !defined(__clang__)
__attribute__((optimize("O3")))
#endif
inline void apply_large(std::uint64_t *a, const std::uint64_t *b, std::size_t n) {
static_assert(Op != Operation::identity);
for (std::size_t i = 0; i < n; ++i) a[i] = combine<Op>(a[i], b[i]);
}
template <Operation Op> inline void apply(std::uint64_t *a, const std::uint64_t *b, std::size_t n) {
static_assert(Op != Operation::identity);
if (n >= 32) return apply_large<Op>(a, b, n);
for (std::size_t i = 0; i < n; ++i) a[i] = combine<Op>(a[i], b[i]);
}
template <Operation Op> inline std::size_t count(const std::uint64_t *a, const std::uint64_t *b, std::size_t n) {
#if defined(__x86_64__) && (defined(__GNUC__) || defined(__clang__))
if (n >= 64) {
if (has_avx512()) return avx512<Op>(a, b, n);
if (has_avx2()) return avx2<Op>(a, b, n);
}
#endif
if (n >= 8) return scalar_large<Op>(a, b, n);
return scalar<Op>(a, b, n);
}
}
#line 5 "data_structure/dynamic_bitset.hpp"
#include <algorithm>
#line 7 "data_structure/dynamic_bitset.hpp"
#include <cassert>
#line 10 "data_structure/dynamic_bitset.hpp"
#include <limits>
#include <span>
#include <stdexcept>
#include <string>
#include <string_view>
#include <utility>
#include <vector>
class [[nodiscard, gnu::warn_unused]] DynamicBitset {
using Word = std::uint64_t;
using Operation = bitset_ops_detail::Operation;
std::vector<Word> data_;
int n_ = 0;
static std::size_t word_count(int n) { return (std::size_t(n) + 63) / 64; }
static Word mask(int n) { return n == 64 ? ~Word(0) : (Word(1) << n) - 1; }
void trim() { if (n_ & 63) data_.back() &= mask(n_ & 63); }
void check([[maybe_unused]] int p) const { assert(0 <= p && p < n_); }
void check_range([[maybe_unused]] int l, [[maybe_unused]] int r) const { assert(0 <= l && l <= r && r <= n_); }
void check_size([[maybe_unused]] const DynamicBitset &other) const { assert(n_ == other.n_); }
Word chosen(std::size_t i, bool value) const {
Word x = value ? data_[i] : ~data_[i];
if (!value && i + 1 == data_.size() && (n_ & 63)) x &= mask(n_ & 63);
return x;
}
Word extract(int p, int length) const {
std::size_t w = unsigned(p) / 64;
int offset = p & 63;
Word x = data_[w] >> offset;
if (offset && length > 64 - offset) x |= data_[w + 1] << (64 - offset);
return x & mask(length);
}
template <class F> void update_range(int l, int r, F apply) {
check_range(l, r);
if (l == r) return;
std::size_t first = unsigned(l) / 64, last = unsigned(r - 1) / 64;
Word left = ~Word(0) << (l & 63), right = mask(((r - 1) & 63) + 1);
if (first == last) { apply(data_[first], left & right); return; }
apply(data_[first], left);
for (auto i = first + 1; i < last; ++i) apply(data_[i], ~Word(0));
apply(data_[last], right);
}
template <Operation Op> int count_with(const DynamicBitset &other) const {
if constexpr (Op == Operation::identity) return int(bitset_ops_detail::count<Op>(data_.data(), nullptr, data_.size()));
if constexpr (Op == Operation::and_not) check_size(other);
std::size_t common = std::min(data_.size(), other.data_.size());
int result = 0;
if (common >= 8) result = int(bitset_ops_detail::count<Op>(data_.data(), other.data_.data(), common));
else for (std::size_t i = 0; i < common; ++i) result += std::popcount(bitset_ops_detail::combine<Op>(data_[i], other.data_[i]));
if constexpr (Op == Operation::bit_or || Op == Operation::bit_xor) {
const auto &tail = data_.size() > other.data_.size() ? data_ : other.data_;
if (common < tail.size()) result += int(bitset_ops_detail::count<Operation::identity>(tail.data() + common, nullptr, tail.size() - common));
}
return result;
}
template <Operation Op> static DynamicBitset binary(const DynamicBitset &a, const DynamicBitset &b) {
bool first = Op == Operation::bit_and ? a.n_ <= b.n_ : a.n_ >= b.n_;
DynamicBitset result = first ? a : b;
const auto &other = first ? b : a;
bitset_ops_detail::apply<Op>(result.data_.data(), other.data_.data(), std::min(result.data_.size(), other.data_.size()));
return result;
}
template <bool Left, bool Or> DynamicBitset &shift(std::size_t amount) {
if (amount >= std::size_t(n_)) { if constexpr (!Or) reset_all(); return *this; }
if (!amount) return *this;
std::size_t skip = amount / 64, length = data_.size();
unsigned bits = amount & 63;
if constexpr (Left) {
for (std::size_t i = length; i-- > skip;) {
Word x = data_[i - skip] << bits;
if (bits && i > skip) x |= data_[i - skip - 1] >> (64 - bits);
if constexpr (Or) data_[i] |= x;
else data_[i] = x;
}
if constexpr (!Or) std::fill(data_.begin(), data_.begin() + skip, 0);
} else {
for (std::size_t i = 0; i < length - skip; ++i) {
Word x = data_[i + skip] >> bits;
if (bits && i + skip + 1 < length) x |= data_[i + skip + 1] << (64 - bits);
if constexpr (Or) data_[i] |= x;
else data_[i] = x;
}
if constexpr (!Or) std::fill(data_.end() - skip, data_.end(), 0);
}
trim();
return *this;
}
static Word reverse_word(Word x) {
x = ((x >> 1) & 0x5555555555555555ULL) | ((x & 0x5555555555555555ULL) << 1);
x = ((x >> 2) & 0x3333333333333333ULL) | ((x & 0x3333333333333333ULL) << 2);
x = ((x >> 4) & 0x0f0f0f0f0f0f0f0fULL) | ((x & 0x0f0f0f0f0f0f0f0fULL) << 4);
return std::byteswap(x);
}
public:
class reference {
Word *word_;
Word mask_;
friend class DynamicBitset;
reference(Word &word, int bit) : word_(&word), mask_(Word(1) << bit) {}
public:
reference(const reference &) = default;
operator bool() const { return (*word_ & mask_) != 0; }
reference &operator=(bool value) { if (value) *word_ |= mask_; else *word_ &= ~mask_; return *this; }
reference &operator=(const reference &other) { return *this = bool(other); }
reference &flip() { *word_ ^= mask_; return *this; }
};
DynamicBitset() = default;
explicit DynamicBitset(int n, bool value = false) : n_(n) {
assert(n >= 0);
data_.assign(word_count(n), value ? ~Word(0) : 0); trim();
}
explicit DynamicBitset(std::string_view text) {
assert(text.size() <= std::size_t(std::numeric_limits<int>::max()));
n_ = int(text.size()); data_.resize(word_count(n_));
for (int i = 0; i < n_; ++i) {
char c = text[std::size_t(n_ - 1 - i)];
if (c != '0' && c != '1') throw std::invalid_argument("DynamicBitset");
if (c == '1') data_[unsigned(i) / 64] |= Word(1) << (i & 63);
}
}
DynamicBitset(const DynamicBitset &) = default;
DynamicBitset &operator=(const DynamicBitset &) = default;
DynamicBitset(DynamicBitset &&other) noexcept { swap(other); }
DynamicBitset &operator=(DynamicBitset &&other) noexcept {
if (this != &other) { DynamicBitset moved(std::move(other)); swap(moved); } return *this;
}
static DynamicBitset from_words(int n, std::span<const Word> words) {
assert(n >= 0 && words.size() == word_count(n));
DynamicBitset result; result.data_.assign(words.begin(), words.end()); result.n_ = n; result.trim(); return result;
}
void swap(DynamicBitset &other) noexcept { data_.swap(other.data_); std::swap(n_, other.n_); }
[[nodiscard]] int size() const { return n_; }
[[nodiscard]] bool empty() const { return !n_; }
[[nodiscard]] std::span<const Word> words() const { return data_; }
[[nodiscard]] bool test(int p) const { check(p); return (data_[unsigned(p) / 64] >> (p & 63)) & 1; }
[[nodiscard]] bool operator[](int p) const { return test(p); }
[[nodiscard]] reference operator[](int p) { check(p); return reference(data_[unsigned(p) / 64], p & 63); }
DynamicBitset &set(int p, bool value = true) { (*this)[p] = value; return *this; }
DynamicBitset &reset(int p) { return set(p, false); }
DynamicBitset &flip(int p) { (*this)[p].flip(); return *this; }
DynamicBitset &set_all(bool value = true) { std::fill(data_.begin(), data_.end(), value ? ~Word(0) : 0); trim(); return *this; }
DynamicBitset &reset_all() { return set_all(false); }
DynamicBitset &flip_all() { for (auto &x : data_) x = ~x; trim(); return *this; }
DynamicBitset &set_range(int l, int r, bool value = true) {
update_range(l, r, [value](Word &x, Word m) { if (value) x |= m; else x &= ~m; }); return *this;
}
DynamicBitset &reset_range(int l, int r) { return set_range(l, r, false); }
DynamicBitset &flip_range(int l, int r) { update_range(l, r, [](Word &x, Word m) { x ^= m; }); return *this; }
void reserve(int n) { assert(n >= 0); data_.reserve(word_count(n)); }
void resize(int n, bool value = false) {
assert(n >= 0);
int old = n_;
data_.resize(word_count(n), 0); n_ = n;
if (n > old && value) set_range(old, n); else trim();
}
void push_back(bool value) { assert(n_ < std::numeric_limits<int>::max()); int p = n_; resize(n_ + 1); set(p, value); }
void pop_back() { assert(n_); resize(n_ - 1); }
void clear() { data_.clear(); n_ = 0; }
[[nodiscard]] int count() const { return count_with<Operation::identity>(*this); }
[[nodiscard]] int count(int l, int r) const {
check_range(l, r); if (l == r) return 0;
std::size_t first = unsigned(l) / 64, last = unsigned(r - 1) / 64;
Word left = ~Word(0) << (l & 63), right = mask(((r - 1) & 63) + 1);
if (first == last) return std::popcount(data_[first] & left & right);
int result = std::popcount(data_[first] & left) + std::popcount(data_[last] & right);
result += int(bitset_ops_detail::count<Operation::identity>(data_.data() + first + 1, nullptr, last - first - 1));
return result;
}
[[nodiscard]] int rank(int r) const { return count(0, r); }
[[nodiscard]] bool any() const { for (auto x : data_) if (x) return true; return false; }
[[nodiscard]] bool none() const { return !any(); }
[[nodiscard]] bool all() const {
std::size_t full = unsigned(n_) / 64;
for (std::size_t i = 0; i < full; ++i) if (data_[i] != ~Word(0)) return false;
return !(n_ & 63) || data_[full] == mask(n_ & 63);
}
[[nodiscard]] int count_and(const DynamicBitset &other) const { return count_with<Operation::bit_and>(other); }
[[nodiscard]] int count_or(const DynamicBitset &other) const { return count_with<Operation::bit_or>(other); }
[[nodiscard]] int count_xor(const DynamicBitset &other) const { return count_with<Operation::bit_xor>(other); }
[[nodiscard]] int count_and_not(const DynamicBitset &other) const { return count_with<Operation::and_not>(other); }
[[nodiscard]] bool intersection_parity(const DynamicBitset &other) const {
check_size(other); Word x = 0;
for (std::size_t i = 0; i < data_.size(); ++i) x ^= data_[i] & other.data_[i];
return std::popcount(x) & 1;
}
[[nodiscard]] bool intersects(const DynamicBitset &other) const { check_size(other); for (std::size_t i = 0; i < data_.size(); ++i) if (data_[i] & other.data_[i]) return true; return false; }
[[nodiscard]] bool is_subset_of(const DynamicBitset &other) const { check_size(other); for (std::size_t i = 0; i < data_.size(); ++i) if (data_[i] & ~other.data_[i]) return false; return true; }
[[nodiscard]] bool is_proper_subset_of(const DynamicBitset &other) const { return is_subset_of(other) && *this != other; }
[[nodiscard]] int compare(const DynamicBitset &other) const {
check_size(other); for (auto i = data_.size(); i-- > 0;) if (data_[i] != other.data_[i]) return data_[i] < other.data_[i] ? -1 : 1; return 0;
}
[[nodiscard]] int find_next(int p, bool value = true) const {
assert(-1 <= p && p < n_); ++p;
if (p == n_) return n_;
std::size_t i = unsigned(p) / 64;
Word x = chosen(i, value) & (~Word(0) << (p & 63));
for (;;) {
if (x) return int(i * 64 + std::countr_zero(x));
if (++i == data_.size()) return n_;
x = chosen(i, value);
}
}
[[nodiscard]] int find_prev(int p, bool value = true) const {
assert(0 <= p && p <= n_); if (!p) return n_; --p;
std::size_t i = unsigned(p) / 64;
Word x = chosen(i, value) & mask((p & 63) + 1);
for (;;) {
if (x) return int(i * 64 + 63 - std::countl_zero(x));
if (!i) return n_;
x = chosen(--i, value);
}
}
[[nodiscard]] int find_first(bool value = true) const { return n_ ? find_next(-1, value) : 0; }
[[nodiscard]] int find_last(bool value = true) const { return find_prev(n_, value); }
[[nodiscard]] int select(int k, bool value = true) const {
assert(k >= 0);
for (std::size_t i = 0; i < data_.size(); ++i) {
Word x = chosen(i, value); int c = std::popcount(x);
if (k < c) { while (k--) x &= x - 1; return int(i * 64 + std::countr_zero(x)); }
k -= c;
}
return n_;
}
template <class F> void for_each(int l, int r, F &&emit) const {
check_range(l, r); if (l == r) return;
for (std::size_t i = unsigned(l) / 64, last = unsigned(r - 1) / 64; i <= last; ++i) {
Word x = data_[i];
if (i == unsigned(l) / 64) x &= ~Word(0) << (l & 63);
if (i == last) x &= mask(((r - 1) & 63) + 1);
while (x) { emit(int(i * 64 + std::countr_zero(x))); x &= x - 1; }
}
}
template <class F> void for_each(F &&emit) const { for_each(0, n_, std::forward<F>(emit)); }
DynamicBitset &operator&=(const DynamicBitset &other) {
if (n_ > other.n_) resize(other.n_);
bitset_ops_detail::apply<Operation::bit_and>(data_.data(), other.data_.data(), data_.size()); return *this;
}
DynamicBitset &operator|=(const DynamicBitset &other) {
if (n_ < other.n_) resize(other.n_);
bitset_ops_detail::apply<Operation::bit_or>(data_.data(), other.data_.data(), other.data_.size()); return *this;
}
DynamicBitset &operator^=(const DynamicBitset &other) {
if (n_ < other.n_) resize(other.n_);
bitset_ops_detail::apply<Operation::bit_xor>(data_.data(), other.data_.data(), other.data_.size()); return *this;
}
DynamicBitset &operator-=(const DynamicBitset &other) { check_size(other); bitset_ops_detail::apply<Operation::and_not>(data_.data(), other.data_.data(), data_.size()); return *this; }
friend DynamicBitset operator&(const DynamicBitset &a, const DynamicBitset &b) { return binary<Operation::bit_and>(a, b); }
friend DynamicBitset operator|(const DynamicBitset &a, const DynamicBitset &b) { return binary<Operation::bit_or>(a, b); }
friend DynamicBitset operator^(const DynamicBitset &a, const DynamicBitset &b) { return binary<Operation::bit_xor>(a, b); }
friend DynamicBitset operator-(DynamicBitset a, const DynamicBitset &b) { a -= b; return a; }
DynamicBitset operator~() const { auto result = *this; result.flip_all(); return result; }
[[nodiscard]] bool operator==(const DynamicBitset &) const = default;
DynamicBitset &operator<<=(std::size_t k) { return shift<true, false>(k); }
DynamicBitset &operator>>=(std::size_t k) { return shift<false, false>(k); }
friend DynamicBitset operator<<(DynamicBitset a, std::size_t k) { a <<= k; return a; }
friend DynamicBitset operator>>(DynamicBitset a, std::size_t k) { a >>= k; return a; }
DynamicBitset &or_shift_left(std::size_t k) { return shift<true, true>(k); }
DynamicBitset &or_shift_right(std::size_t k) { return shift<false, true>(k); }
void copy_range(int dst, const DynamicBitset &source, int l, int r) {
source.check_range(l, r); assert(0 <= dst && r - l <= n_ - dst);
int length = r - l;
auto copy = [&](int offset, int count) {
Word x = source.extract(l + offset, count);
int p = dst + offset; Word m = mask(count) << (p & 63);
auto &target = data_[unsigned(p) / 64]; target = (target & ~m) | (x << (p & 63));
};
if (this == &source && dst > l) {
while (length) { int count = std::min(length, ((dst + length - 1) & 63) + 1); length -= count; copy(length, count); }
} else {
for (int offset = 0; offset < length;) { int count = std::min(length - offset, 64 - ((dst + offset) & 63)); copy(offset, count); offset += count; }
}
}
DynamicBitset slice(int l, int r) const { check_range(l, r); DynamicBitset result(r - l); result.copy_range(0, *this, l, r); return result; }
void append(const DynamicBitset &other) {
int length = other.n_, old = n_; assert(length <= std::numeric_limits<int>::max() - old);
resize(old + length); copy_range(old, other, 0, length);
}
DynamicBitset &reverse() {
std::reverse(data_.begin(), data_.end()); for (auto &x : data_) x = reverse_word(x);
if (n_ & 63) {
unsigned bits = 64 - (n_ & 63);
for (std::size_t i = 0; i < data_.size(); ++i)
data_[i] = (data_[i] >> bits) | (i + 1 < data_.size() ? data_[i + 1] << (64 - bits) : 0);
}
return *this;
}
DynamicBitset &rotate_left(std::size_t amount) {
if (!n_ || !(amount %= std::size_t(n_))) return *this;
auto wrap = *this; wrap >>= std::size_t(n_) - amount; *this <<= amount; return *this |= wrap;
}
DynamicBitset &rotate_right(std::size_t amount) { if (n_ && (amount %= std::size_t(n_))) rotate_left(std::size_t(n_) - amount); return *this; }
[[nodiscard]] std::string to_string() const {
std::string result(n_, '0'); for_each([&](int p) { result[std::size_t(n_ - 1 - p)] = '1'; }); return result;
}
};
#line 1 "components/fast_io.hpp"
#line 5 "components/fast_io.hpp"
#include <array>
#line 8 "components/fast_io.hpp"
#include <charconv>
#line 11 "components/fast_io.hpp"
#include <cstdio>
#include <cstring>
#include <memory>
#line 17 "components/fast_io.hpp"
#include <type_traits>
#if defined(__unix__) || defined(__APPLE__)
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>
#endif
namespace fast_io_detail { struct BulkInput; struct BulkOutput; }
class FastInput {
friend struct fast_io_detail::BulkInput;
static constexpr std::size_t capacity = 1 << 16;
FILE *file = nullptr;
std::unique_ptr<char[]> buffer;
const char *current = "", *end = current;
std::string scratch;
void *mapping = nullptr;
std::size_t mapped_size = 0;
bool refill() {
if (!file) return false;
std::size_t n = std::fread(buffer.get(), 1, capacity, file);
current = buffer.get();
end = current + n;
return n;
}
static const char *scan(const char *p, const char *end) {
while (end - p >= 8) {
std::uint64_t x;
std::memcpy(&x, p, 8);
if ((x - 0x2121212121212121ULL) & ~x & 0x8080808080808080ULL) break;
p += 8;
}
while (p != end && static_cast<unsigned char>(*p) > ' ') ++p;
return p;
}
public:
explicit FastInput(FILE *input = stdin) {
#if defined(__unix__) || defined(__APPLE__)
struct stat status;
int fd = fileno(input);
auto offset = ftello(input);
if (fd >= 0 && offset >= 0 && !fstat(fd, &status) && S_ISREG(status.st_mode) && status.st_size > offset) {
mapped_size = status.st_size;
mapping = mmap(nullptr, mapped_size, PROT_READ, MAP_PRIVATE, fd, 0);
if (mapping != MAP_FAILED) {
current = static_cast<const char *>(mapping) + offset;
end = static_cast<const char *>(mapping) + mapped_size;
return;
}
mapping = nullptr;
}
#endif
file = input;
buffer = std::make_unique_for_overwrite<char[]>(capacity);
}
explicit FastInput(std::string_view input) : current(input.empty() ? "" : input.data()), end(current + input.size()) {}
FastInput(const FastInput &) = delete;
FastInput &operator=(const FastInput &) = delete;
~FastInput() {
#if defined(__unix__) || defined(__APPLE__)
if (mapping) munmap(mapping, mapped_size);
#endif
}
std::string_view token() {
while (true) {
while (current != end && static_cast<unsigned char>(*current) <= ' ') ++current;
if (current != end) break;
if (!refill()) return {};
}
const char *begin = current;
current = scan(current, end);
if (current != end || !file) return {begin, std::size_t(current - begin)};
scratch.assign(begin, end);
while (refill()) {
current = scan(current, end);
scratch.append(buffer.get(), std::size_t(current - buffer.get()));
if (current != end) break;
}
return scratch;
}
template <class T>
bool read(T &value) {
if constexpr (std::is_integral_v<T> && !std::is_same_v<T, bool>) {
while (true) {
while (current != end && static_cast<unsigned char>(*current) <= ' ') ++current;
if (current != end) break;
if (!refill()) return false;
}
if constexpr (std::is_unsigned_v<T> && sizeof(T) == 4 && std::endian::native == std::endian::little) {
if (end - current >= 11) {
std::uint64_t x;
std::memcpy(&x, current, 8);
if (!(((x + 0x4646464646464646ULL) | (x - 0x3030303030303030ULL)) & 0x8080808080808080ULL)) {
x &= 0x0f0f0f0f0f0f0f0fULL;
x = (x * 10 + (x >> 8)) & 0x00ff00ff00ff00ffULL;
x = (x * 100 + (x >> 16)) & 0x0000ffff0000ffffULL;
std::uint64_t v = std::uint32_t(x * 10000 + (x >> 32));
int n = 8;
for (; n < 10 && static_cast<unsigned char>(current[n]) - unsigned('0') < 10; ++n)
v = v * 10 + (current[n] - '0');
if (static_cast<unsigned char>(current[n]) <= ' ' && v <= 0xffffffffULL) {
current += n;
value = T(v);
return true;
}
}
}
}
T parsed{};
auto result = std::from_chars(current, end, parsed);
if (result.ec == std::errc{} && (result.ptr != end ? static_cast<unsigned char>(*result.ptr) <= ' ' : !file)) {
current = result.ptr;
value = parsed;
return true;
}
}
auto s = token();
if (s.empty()) return false;
if constexpr (std::is_same_v<T, bool>) {
assert(s == "0" || s == "1");
value = s[0] == '1';
} else if constexpr (std::is_integral_v<T>) {
auto result = std::from_chars(s.data(), s.data() + s.size(), value);
assert(result.ec == std::errc{} && result.ptr == s.data() + s.size());
(void)result;
} else value = T(s);
return true;
}
};
class FastOutput {
friend struct fast_io_detail::BulkOutput;
inline static constexpr auto quads = [] {
std::array<std::array<char, 4>, 10000> table{};
for (int i = 0; i < 10000; ++i)
table[i] = {char('0' + i / 1000), char('0' + i / 100 % 10), char('0' + i / 10 % 10), char('0' + i % 10)};
return table;
}();
FILE *file;
std::unique_ptr<char[]> buffer = std::make_unique_for_overwrite<char[]>(1 << 16);
std::size_t capacity = 1 << 16, length = 0;
char *reserve(std::size_t n) {
if (n > capacity - length) {
if (!flush()) throw std::runtime_error("output failed");
if (n > capacity) {
std::size_t next = std::max(n, 2 * capacity);
buffer = std::make_unique_for_overwrite<char[]>(next);
capacity = next;
}
}
return buffer.get() + length;
}
public:
explicit FastOutput(FILE *output = stdout) : file(output) {}
FastOutput(const FastOutput &) = delete;
FastOutput &operator=(const FastOutput &) = delete;
~FastOutput() { flush(); }
bool flush() {
std::size_t offset = 0;
while (offset < length) {
auto n = std::fwrite(buffer.get() + offset, 1, length - offset, file);
if (!n) {
std::memmove(buffer.get(), buffer.get() + offset, length - offset);
length -= offset;
return false;
}
offset += n;
}
length = 0;
return std::fflush(file) == 0;
}
void write(char c) { *reserve(1) = c; ++length; }
void write(__uint128_t value) {
char digits[40];
char *end = digits + sizeof(digits), *begin = end;
do { *--begin = char('0' + value % 10); value /= 10; } while (value);
write(std::string_view(begin, end - begin));
}
void write(__int128_t value) {
__uint128_t magnitude = __uint128_t(value);
if (value < 0) write('-'), magnitude = 0 - magnitude;
write(magnitude);
}
void write(std::string_view s) {
char *out = reserve(s.size());
if (!s.empty()) std::memcpy(out, s.data(), s.size());
length += s.size();
}
template <class T> requires std::is_integral_v<T>
void write(T value) {
char *out = reserve(32);
if constexpr (std::is_same_v<T, bool>) *out = '0' + value, ++length;
else if constexpr (std::is_unsigned_v<T> && sizeof(T) == 4) {
char *p = out;
if (value >= 100000000) {
auto high = value / 100000000, low = value % 100000000;
p = std::to_chars(p, p + 2, high).ptr;
std::memcpy(p, quads[low / 10000].data(), 4);
std::memcpy(p + 4, quads[low % 10000].data(), 4);
p += 8;
} else if (value >= 10000) {
p = std::to_chars(p, p + 4, value / 10000).ptr;
std::memcpy(p, quads[value % 10000].data(), 4);
p += 4;
} else p = std::to_chars(p, p + 4, value).ptr;
length += p - out;
} else length += std::to_chars(out, out + 32, value).ptr - out;
}
template <class T> requires requires(const T &value, char *out) { value.decimal_capacity(); value.to_chars(out); }
void write(const T &value) {
char *out = reserve(value.decimal_capacity());
length += value.to_chars(out) - out;
}
template <class T>
void println(const T &value) { write(value); write('\n'); }
};
#line 4 "test/dynamic_bitset_matrix_product.test.cpp"
int main() {
FastInput in;
FastOutput out;
int n = 0, m = 0, k = 0;
in.read(n); in.read(m); in.read(k);
std::vector<DynamicBitset> rows;
rows.reserve(n);
for (int i = 0; i < n; ++i) rows.emplace_back(in.token());
std::vector<DynamicBitset> columns(k, DynamicBitset(m));
for (int i = 0; i < m; ++i) {
auto row = in.token();
for (int j = 0; j < k; ++j) if (row[j] == '1') columns[j].set(m - 1 - i);
}
std::string row(k, '0');
for (const auto &bits : rows) {
for (int j = 0; j < k; ++j) row[j] = char('0' + bits.intersection_parity(columns[j]));
out.println(row);
}
}