verify/yosupo/data-structure/bitset/matrix_product_mod_2.test.cpp

• View this file on GitHub
• Last update: 2026-10-24 00:10:28+07:00
• Problem: https://judge.yosupo.jp/problem/matrix_product_mod_2

Depends on

• data-structure/bitset.hpp
• template.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/matrix_product_mod_2"
#include "template.hpp"
#include "data-structure/bitset.hpp"

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,m,k;
    cin >> n >> m >> k;
    vector<BitSet> a(n,BitSet(m)),b(m,BitSet(k));
    for(int i=0;i<n;i++){
        string s;
        cin >> s;
        for(int j=0;j<m;j++)if(s[j]=='1')a[i].set(j);
    }
    for(int i=0;i<m;i++){
        string s;
        cin >> s;
        for(int j=0;j<k;j++)if(s[j]=='1')b[i].set(j);
    }
    for(int i=0;i<n;i++){
        BitSet c(k);
        for(int j=a[i].find_first();j<m;j=a[i].find_next(j+1))c^=b[j];
        string s(k,'0');
        for(int j=0;j<k;j++)if(c[j])s[j]='1';
        cout << s << "\n";
    }
}

#line 1 "verify/yosupo/data-structure/bitset/matrix_product_mod_2.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/matrix_product_mod_2"
#line 2 "template.hpp"
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using db = long double;
using i128 = __int128_t;
using u32 = uint32_t;
using u64 = uint64_t;
template<class T>
using PQ = priority_queue<T,vector<T>,greater<T>>;

const int INF=INT_MAX/2;
const ll LINF=LLONG_MAX/4;
const db DINF=numeric_limits<db>::infinity();
const db EPS=1e-9;
const db PI=acos(db(-1));

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define SZ(a) (int)(a.size())
#define SORT(a) sort(ALL(a))
#define RSORT(a) sort(RALL(a))
#define REV(a) reverse(ALL(a))
#define UNI(a) a.erase(unique(ALL(a)),a.end())
#define LB(a,x) (int)(lower_bound(ALL(a),x)-a.begin())
#define UB(a,x) (int)(upper_bound(ALL(a),x)-a.begin())
#define FIND(a,x) (int)(find(ALL(a),x)-a.begin())
#define COUNT(a,x) (int)count(ALL(a),x)
#define MIN(a) *min_element(ALL(a))
#define MAX(a) *max_element(ALL(a))

template<class T,class U>
bool chmin(T &a,U b){return b<a?a=b,1:0;}
template<class T,class U>
bool chmax(T &a,U b){return a<b?a=b,1:0;}

template<class T>
T floor(T a,T b){return a/b-((a^b)<0&&a%b);}
template<class T>
T ceil(T a,T b){return a/b+((a^b)>=0&&a%b);}

int popcnt(ll x){return __builtin_popcountll(x);}
int topbit(ll x){return x==0?-1:63-__builtin_clzll(x);}
int lowbit(ll x){return x==0?-1:__builtin_ctzll(x);}

template<class T,class U>
T SUM(const U &a){return accumulate(ALL(a),T{});}
template<class T>
vector<int> argsort(const vector<T> &a){
    vector<int> p(SZ(a));
    iota(ALL(p),0);
    stable_sort(ALL(p),[&](int i,int j){return a[i]<a[j];});
    return p;
}

template<class T,size_t D=0>
struct VecBuilder{
    array<size_t,D> d;
    VecBuilder<T,D+1> operator[](size_t n)const{
        VecBuilder<T,D+1> res{};
        for(size_t i=0;i<D;i++)res.d[i]=d[i];
        res.d[D]=n;
        return res;
    }
    template<size_t I=0>
    auto build(const T &x)const{
        if constexpr(I+1==D)return vector<T>(d[I],x);
        else return vector<decltype(build<I+1>(x))>(d[I],build<I+1>(x));
    }
    auto operator()(const T &x=T())const{
        static_assert(D>0);
        return build(x);
    }
};
template<class T>
inline constexpr VecBuilder<T> VEC{};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
#line 2 "data-structure/bitset.hpp"

struct BitSet{
    using u64 = uint64_t;
    vector<u64> dat;
    int n;
    
    static u64 maskbit(int p){return 1ULL<<p;}

    struct Proxy{
        u64 &dat;
        int idx;
        Proxy(vector<u64> &d,int i):dat(d[i>>6]),idx(i&63){}
        operator bool()const{return (dat>>idx)&1;}
        bool operator~()const{return ((dat>>idx)&1)^1;}
        Proxy &flip(){dat^=maskbit(idx);return *this;}
        Proxy &operator=(bool x){
            if(x)dat|=maskbit(idx);
            else dat&=~maskbit(idx);
            return *this;
        }
        Proxy &operator=(const Proxy &o){return *this=bool(o);}
        Proxy &operator|=(bool x){if(x)dat|=maskbit(idx);return *this;}
        Proxy &operator&=(bool x){if(!x)dat&=~maskbit(idx);return *this;}
        Proxy &operator^=(bool x){if(x)dat^=maskbit(idx);return *this;}
    };

    explicit BitSet(int _n=0,bool x=false):dat((_n+63)>>6,u64(x?-1:0)),n(_n){trim();}

    int size()const{return n;}
    void trim(){if(n&63)dat.back()&=maskbit(n&63)-1;}
    void resize(int m,bool x=false){
        assert(m>=0);
        if(x&&n<m&&(n&63))dat[n>>6]|=u64(-1)<<(n&63);
        dat.resize((m+63)>>6,u64(x?-1:0));
        n=m;
        trim();
    }
    void push_back(bool x){
        if((n&63)==0)dat.push_back(0);
        if(x)dat[n>>6]|=maskbit(n&63);
        n++;
    }
    void pop_back(){
        assert(n>0);
        n--;
        if((n&63)==0)dat.pop_back();
        else dat.back()&=maskbit(n&63)-1;
    }

    Proxy operator[](int i){
        assert(0<=i&&i<n);
        return Proxy(dat,i);
    }
    bool operator[](int i)const{
        assert(0<=i&&i<n);
        return (dat[i>>6]>>(i&63))&1;
    }

    void set(){fill(ALL(dat),u64(-1));trim();}
    void reset(){fill(ALL(dat),0);}
    void flip(){for(auto &x:dat)x=~x;trim();}
    void set(int i){(*this)[i]=1;}
    void reset(int i){(*this)[i]=0;}
    void flip(int i){(*this)[i].flip();}

    int count()const{
        int res=0;
        for(auto x:dat)res+=__builtin_popcountll(x);
        return res;
    }
    bool any()const{
        for(auto x:dat)if(x)return true;
        return false;
    }
    bool none()const{return !any();}
    bool all()const{return count()==n;}

    BitSet &operator&=(const BitSet &o){
        assert(n==o.n);
        for(int i=0;i<SZ(dat);i++)dat[i]&=o.dat[i];
        return *this;
    }
    BitSet &operator|=(const BitSet &o){
        assert(n==o.n);
        for(int i=0;i<SZ(dat);i++)dat[i]|=o.dat[i];
        return *this;
    }
    BitSet &operator^=(const BitSet &o){
        assert(n==o.n);
        for(int i=0;i<SZ(dat);i++)dat[i]^=o.dat[i];
        return *this;
    }
    BitSet &operator<<=(int k){
        assert(k>=0);
        if(k>=n)return reset(),*this;
        int q=k>>6,r=k&63,m=SZ(dat);
        if(!r){
            for(int i=m-1;i>=q;i--)dat[i]=dat[i-q];
        }else{
            for(int i=m-1;i>q;i--)dat[i]=(dat[i-q]<<r)|(dat[i-q-1]>>(64-r));
            dat[q]=dat[0]<<r;
        }
        fill(dat.begin(),dat.begin()+q,0);
        trim();
        return *this;
    }
    BitSet &operator>>=(int k){
        assert(k>=0);
        if(k>=n)return reset(),*this;
        int q=k>>6,r=k&63,m=SZ(dat);
        if(!r){
            for(int i=0;i+q<m;i++)dat[i]=dat[i+q];
        }else{
            for(int i=0;i+q+1<m;i++)dat[i]=(dat[i+q]>>r)|(dat[i+q+1]<<(64-r));
            dat[m-q-1]=dat[m-1]>>r;
        }
        fill(dat.end()-q,dat.end(),0);
        return *this;
    }
    BitSet operator&(const BitSet &o)const{return BitSet(*this)&=o;}
    BitSet operator|(const BitSet &o)const{return BitSet(*this)|=o;}
    BitSet operator^(const BitSet &o)const{return BitSet(*this)^=o;}
    BitSet operator<<(int k)const{return BitSet(*this)<<=k;}
    BitSet operator>>(int k)const{return BitSet(*this)>>=k;}
    bool operator==(const BitSet &o){return n==o.n&&dat==o.dat;}
    bool operator!=(const BitSet &o){return !(*this==o);}
    BitSet operator~()const{
        BitSet o(*this);
        o.flip();
        return o;
    }

    int find_next(int i)const{ // first set bit >= i, n if none
        if(i<0)i=0;
        if(i>=n)return n;
        int q=i>>6;
        u64 x=dat[q]&(u64(-1)<<(i&63));
        while(!x){
            if(++q==SZ(dat))return n;
            x=dat[q];
        }
        return q<<6|__builtin_ctzll(x);
    }
    int find_prev(int i)const{ // last set bit <= i, -1 if none
        if(i>=n)i=n-1;
        if(i<0)return -1;
        int q=i>>6;
        u64 x=dat[q]&(u64(-1)>>(63-(i&63)));
        while(!x){
            if(--q<0)return -1;
            x=dat[q];
        }
        return q<<6|(63-__builtin_clzll(x));
    }
    int find_first()const{return find_next(0);}
    int find_last()const{return find_prev(n-1);}

    void set_range(int l,int r){
        assert(0<=l&&l<=r&&r<=n);
        if(l==r)return;
        int ql=l>>6,qr=r>>6;
        u64 ml=u64(-1)<<(l&63),mr=maskbit(r&63)-1;
        if(ql==qr)return void(dat[ql]|=ml&mr);
        if(l&63)dat[ql++]|=ml;
        if(r&63)dat[qr]|=mr;
        for(int i=ql;i<qr;i++)dat[i]=u64(-1);
    }
    void reset_range(int l,int r){
        assert(0<=l&&l<=r&&r<=n);
        if(l==r)return;
        int ql=l>>6,qr=r>>6;
        u64 ml=u64(-1)<<(l&63),mr=maskbit(r&63)-1;
        if(ql==qr)return void(dat[ql]&=~(ml&mr));
        if(l&63)dat[ql++]&=~ml;
        if(r&63)dat[qr]&=~mr;
        for(int i=ql;i<qr;i++)dat[i]=u64(0);
    }
    void flip_range(int l,int r){
        assert(0<=l&&l<=r&&r<=n);
        if(l==r)return;
        int ql=l>>6,qr=r>>6;
        u64 ml=u64(-1)<<(l&63),mr=maskbit(r&63)-1;
        if(ql==qr)return void(dat[ql]^=ml&mr);
        if(l&63)dat[ql++]^=ml;
        if(r&63)dat[qr]^=mr;
        for(int i=ql;i<qr;i++)dat[i]=~dat[i];
    }
    int count_range(int l,int r)const{
        assert(0<=l&&l<=r&&r<=n);
        if(l==r)return 0;
        int ql=l>>6,qr=r>>6;
        u64 ml=u64(-1)<<(l&63),mr=maskbit(r&63)-1;
        if(ql==qr)return __builtin_popcountll(dat[ql]&ml&mr);
        int res=0;
        if(l&63)res+=__builtin_popcountll(dat[ql++]&ml);
        if(r&63)res+=__builtin_popcountll(dat[qr]&mr);
        for(int i=ql;i<qr;i++)res+=__builtin_popcountll(dat[i]);
        return res;
    }
};
#line 4 "verify/yosupo/data-structure/bitset/matrix_product_mod_2.test.cpp"

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,m,k;
    cin >> n >> m >> k;
    vector<BitSet> a(n,BitSet(m)),b(m,BitSet(k));
    for(int i=0;i<n;i++){
        string s;
        cin >> s;
        for(int j=0;j<m;j++)if(s[j]=='1')a[i].set(j);
    }
    for(int i=0;i<m;i++){
        string s;
        cin >> s;
        for(int j=0;j<k;j++)if(s[j]=='1')b[i].set(j);
    }
    for(int i=0;i<n;i++){
        BitSet c(k);
        for(int j=a[i].find_first();j<m;j=a[i].find_next(j+1))c^=b[j];
        string s(k,'0');
        for(int j=0;j<k;j++)if(c[j])s[j]='1';
        cout << s << "\n";
    }
}

Back to top page