Submission #24717118

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#line 1 "main.cpp"
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define rep3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define repr(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define rep3r(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
using namespace std;
#line 1 "/usr/local/kyopro/math/linear_equation_bin.hpp"
/**
 * @brief 掃き出し法 (binary行列)
 * original: https://github.com/drken1215/algorithm/blob/2eadcda21d142c36a50774bee10465caaa4f8022/MathAlgebra/matrix_binary.cpp
 */
#line 8 "/usr/local/kyopro/math/linear_equation_bin.hpp"
const int MAX_ROW = 510; // to be set appropriately
const int MAX_COL = 510; // to be set appropriately
struct BitMatrix {
    int H, W;
    std::bitset<MAX_COL> val[MAX_ROW];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#line 1 "main.cpp"
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define rep3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define repr(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define rep3r(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
using namespace std;

#line 1 "/usr/local/kyopro/math/linear_equation_bin.hpp"
/**
 * @brief 掃き出し法 (binary行列)
 * original: https://github.com/drken1215/algorithm/blob/2eadcda21d142c36a50774bee10465caaa4f8022/MathAlgebra/matrix_binary.cpp
 */
#line 8 "/usr/local/kyopro/math/linear_equation_bin.hpp"

const int MAX_ROW = 510; // to be set appropriately
const int MAX_COL = 510; // to be set appropriately
struct BitMatrix {
    int H, W;
    std::bitset<MAX_COL> val[MAX_ROW];
    BitMatrix(int m = 1, int n = 1) : H(m), W(n) {}
    inline std::bitset<MAX_COL>& operator [] (int i) {return val[i];}
    inline friend std::ostream& operator << (std::ostream& s, BitMatrix M) {
        s << std::endl;
        for (int i = 0; i < M.H; ++i) {
            for (int j = 0; j < M.W; ++j) s << M.val[i][j];
            s << std::endl;
        }
        return s;
    }
};

int GaussJordan(BitMatrix &A, bool is_extended = false) {
    int rank = 0;
    for (int col = 0; col < A.W; ++col) {
        if (is_extended && col == A.W - 1) break;
        int pivot = -1;
        for (int row = rank; row < A.H; ++row) {
            if (A[row][col]) {
                pivot = row;
                break;
            }
        }
        if (pivot == -1) continue;
        swap(A[pivot], A[rank]);
        for (int row = 0; row < A.H; ++row) {
            if (row != rank && A[row][col]) A[row] ^= A[rank];
        }
        ++rank;
    }
    return rank;
}

int linear_equation(BitMatrix &A, std::vector<int> &b, std::vector<int> &res) {
    int m = A.H, n = A.W;
    BitMatrix M(m, n + 1);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) M[i][j] = A[i][j];
        M[i][n] = b[i];
    }
    int rank = GaussJordan(M, true);

    // check if it has no solution
    for (int row = rank; row < m; ++row) if (M[row][n]) return -1;

    // answer
    res.assign(n, 0);
    for (int i = 0; i < rank; ++i) res[i] = M[i][n];
    return rank;
}
#line 1 "/usr/local/kyopro/math/modint.hpp"
// @title mod int
#line 3 "/usr/local/kyopro/math/modint.hpp"
using ll = long long;

#ifdef MUTABLE
int mod;
#else
template<int mod>
#endif
struct ModInt {
  int val;
  ModInt inv() const{
    int tmp,a=val,b=mod,x=1,y=0;
    while(b)tmp=a/b,a-=tmp*b,std::swap(a,b),x-=tmp*y,std::swap(x,y);
    return ModInt(x);
  }
  ModInt():val(0){}
  ModInt(ll x){if((val=x%mod)<0)val+=mod;}
  ModInt pow(ll t){ModInt res=1,b=*this; while(t){if(t&1)res*=b;b*=b;t>>=1;}return res;}
  ModInt& operator+=(const ModInt& x){if((val+=x.val)>=mod)val-=mod;return *this;}
  ModInt& operator-=(const ModInt& x){if((val+=mod-x.val)>=mod)val-=mod; return *this;}
  ModInt& operator*=(const ModInt& x){val=(ll)val*x.val%mod; return *this;}
  ModInt& operator/=(const ModInt& x){return *this*=x.inv();}
  bool operator==(const ModInt& x) const{return val==x.val;}
  bool operator!=(const ModInt& x) const{return val!=x.val;}
  bool operator<(const ModInt& x) const{return val<x.val;}
  bool operator<=(const ModInt& x) const{return val<=x.val;}
  bool operator>(const ModInt& x) const{return val>x.val;}
  bool operator>=(const ModInt& x) const{return val>=x.val;}
  ModInt operator+(const ModInt& x) const{return ModInt(*this)+=x;}
  ModInt operator-(const ModInt& x) const{return ModInt(*this)-=x;}
  ModInt operator*(const ModInt& x) const{return ModInt(*this)*=x;}
  ModInt operator/(const ModInt& x) const{return ModInt(*this)/=x;}
  friend std::ostream& operator<<(std::ostream& os, const ModInt& mi) { os << mi.val; return os; }
  static int get_mod() { return mod; }
};

constexpr int MOD10 = 1000000007;
constexpr int MOD99 =  998244353;
#ifndef MUTABLE
using modint = ModInt<MOD10>;
using modint99 = ModInt<MOD99>;
#endif
#line 11 "main.cpp"

int main() {
    int n, m; cin >> n >> m;
    BitMatrix A(m, n);
    rep(i,n) {
        int t; cin >> t;
        rep(j,t) {
            int a; cin >> a; --a;
            A[a][i] = 1;
        }
    }
    vector<int> b(m);
    rep(i,m) { cin >> b[i]; }
    vector<int> res(m);
    int rank = linear_equation(A, b, res);
    if (rank == -1) {
        cout << 0 << endl;
        return 0;
    }
    modint99 ans = modint99(2).pow(n-rank);
    cout << ans << endl;

    return 0;
}

Submission Info

Judge Result