結果
| 問題 | No.2134 -algebra over Finite Set |
| ユーザー |
 asaringo
|
| 提出日時 | 2023-11-05 09:59:11 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 11,775 bytes |
| コンパイル時間 | 2,431 ms |
| コンパイル使用メモリ | 215,460 KB |
| 最終ジャッジ日時 | 2025-02-17 19:21:28 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 11 WA * 6 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define overload2(a, b, c, ...) c#define overload3(a, b, c, d, ...) d#define overload4(a, b, c, d, e ...) e#define overload5(a, b, c, d, e, f ...) f#define overload6(a, b, c, d, e, f, g ...) g#define fast_io ios::sync_with_stdio(false); cin.tie(nullptr);#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")typedef long long ll;typedef long double ld;#define chmin(a,b) a = min(a,b);#define chmax(a,b) a = max(a,b);#define bit_count(x) __builtin_popcountll(x)#define leading_zero_count(x) __builtin_clz(x)#define trailing_zero_count(x) __builtin_ctz(x)#define gcd(a,b) __gcd(a,b)#define lcm(a,b) a / gcd(a,b) * b#define rep(...) overload3(__VA_ARGS__, rrep, rep1)(__VA_ARGS__)#define rep1(i,n) for(int i = 0 ; i < n ; i++)#define rrep(i,a,b) for(int i = a ; i < b ; i++)#define repi(it,S) for(auto it = S.begin() ; it != S.end() ; it++)#define pt(a) cout << a << endl;#define print(...) printall(__VA_ARGS__);#define debug(a) cout << #a << " " << a << endl;#define all(a) a.begin(), a.end()#define endl "\n";#define v1(T,n,a) vector<T>(n,a)#define v2(T,n,m,a) vector<vector<T>>(n,v1(T,m,a))#define v3(T,n,m,k,a) vector<vector<vector<T>>>(n,v2(T,m,k,a))#define v4(T,n,m,k,l,a) vector<vector<vector<vector<T>>>>(n,v3(T,m,k,l,a))template<typename T,typename U>istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}template<typename T,typename U>ostream &operator<<(ostream&os,const pair<T,U>&p){os<<p.first<<" "<<p.second;return os;}template<typename T>istream &operator>>(istream&is,vector<T>&v){for(T &in:v){is>>in;}return is;}template<typename T>ostream &operator<<(ostream&os,const vector<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}returnos;}template<typename T>istream &operator>>(istream&is,vector<vector<T>>&v){for(T &in:v){is>>in;}return is;}template<typename T>ostream &operator<<(ostream&os,const vector<vector<T>>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?"\n":"");}return os;}template<typename T>ostream &operator<<(ostream&os,const set<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}template<typename T>ostream &operator<<(ostream&os,const multiset<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}returnos;}template<class... Args> void printall(Args... args){for(auto i:initializer_list<common_type_t<Args...>>{args...}) cout<<i<<" ";cout<<endl;}template<int MAX_COL, typename T=bool> struct BitMatrix{private:int row, col;vector<bitset<MAX_COL>> mat;void init_(vector<vector<T>> A){row = A.size();col = A[0].size();mat.resize(row);for(int i = 0; i < row; i++){for(int j = 0; j < col; j++){if(A[i][j] != 0) mat[i][j] = 1;else mat[i][j] = 0;}}}void init_(vector<T> A, bool row_matrix = false){if(row_matrix) {col = (int)A.size();row = 1;mat.resize(1);for(int i = 0; i < col; i++){if(A[i] != 0) mat[0][i] = 1;else mat[0][i] = 0;}}else {col = 1;row = (int)A.size();mat.resize(row);for(int i = 0; i < row; i++){if(A[i] != 0) mat[i][0] = 1;else mat[i][0] = 0;}}}void transpose_() {vector<bitset<MAX_COL>> res(col);rep(i,row) rep(j,col) res[j][i] = mat[i][j];mat = res;swap(row,col);}void flip_() {rep(i,row) rep(j,col) mat[i][j].flip();}void concat_col_(vector<T> &Y) {BitMatrix X(Y);concat_col_(X);}void concat_col_(vector<vector<T>> &Y) {BitMatrix X(Y);concat_col_(X);}void concat_col_(BitMatrix &Y) {assert((int)Y.row == row);rep(i,row) {rep(j,Y.col) mat[i][j+col] = (Y.mat[i][j]);}col += Y.col;}void concat_row_(vector<T> &Y) {BitMatrix X(Y,true);concat_row_(X);}void concat_row_(vector<vector<T>> &Y) {BitMatrix X(Y);concat_row_(X);}void concat_row_(BitMatrix &Y) {assert((int)Y.col == col);row += Y.row;rep(i,Y.row) mat.push_back(Y.mat[i]);}void print_() {rep(i,row){rep(j,col) cout << mat[i][j]; cout << endl;}}public:inline BitMatrix &operator&=(const BitMatrix Y) {rep(i,row) mat[i] &= Y.mat[i];return *this ;}inline BitMatrix &operator|=(const BitMatrix Y) {rep(i,row) mat[i] |= Y.mat[i];return *this ;}inline BitMatrix &operator^=(const BitMatrix Y) {rep(i,row) mat[i] ^= Y.mat[i];return *this ;}inline BitMatrix operator&(const BitMatrix Y) const { return BitMatrix(*this) &= Y; }inline BitMatrix operator|(const BitMatrix Y) const { return BitMatrix(*this) |= Y; }inline BitMatrix operator^(const BitMatrix Y) const { return BitMatrix(*this) += Y; }inline bool operator==(const BitMatrix Y) const { return mat == Y.mat; }inline bool operator!=(const BitMatrix Y) const { return mat != Y.mat; }inline bitset<MAX_COL>&operator[] (int i) {return mat[i]; }BitMatrix(int n): row(n), col(0) { mat.resize(row); }BitMatrix(vector<T> A, bool row_matrix = false) { init_(A, row_matrix); }BitMatrix(vector<vector<T>> A){ init_(A); }void init(vector<T> A, bool row_matrix = false) { init_(A, row_matrix); }void init(vector<vector<T>> A) { init_(A); }size_t row_size() { return row; }size_t col_size() { return col; }void transpose() { transpose_(); }void flip() { flip_(); }void concat_col(vector<vector<T>> &Y) { concat_col_(Y); }void concat_col(vector<T> &Y) { concat_col_(Y); }void concat_col(BitMatrix &Y) { concat_col_(Y); }void concat_row(vector<vector<T>> &Y) { concat_row_(Y); }void concat_row(vector<T> &Y) { concat_row_(Y); }void concat_row(BitMatrix &Y) { concat_row_(Y); }};const int MAX_COL = 2520;using Matrix = BitMatrix<MAX_COL, bool>;template<typename T=bool> struct GaussJordan{private:int rank;vector<bool> solution;int sweep_out_(Matrix &A , bool is_extended = false){rank = 0 ;for(int col = 0 ; col < A.col_size() ; col++){if(is_extended && col == A.col_size() - 1) break ;int pivot = -1 ;for(int row = rank ; row < A.row_size() ; row++){if(A[row][col]){pivot = row ;break ;}}if(pivot == -1) continue ;swap(A[pivot] , A[rank]) ;for(int row = 0 ; row < A.row_size() ; row++){if(row != rank && A[row][col]) A[row] ^= A[rank] ;}rank++ ;}return rank ;}vector<vector<bool>> create_xorbase_(Matrix &A, bool sorted = false){int r = sweep_out_(A, false), now = 0;for(int i = A.col_size() - 1; i >= 0; i--){int pivot = -1;for(int j = now; j < r; j++){if(A[j][i]) pivot = j;}if(pivot == -1) continue;swap(A[now], A[pivot]);for(int j = 0; j < r; j++){if(j != now && A[j][i]) A[j] ^= A[now];}now++;}vector<vector<bool>> res(r,vector<bool>(A.col_size(),0));for(int i = 0; i < r; i++){for(int j = 0; j < A.col_size(); j++) if(A[i][j]) res[i][j] = true;}if(sorted) reverse(res.begin(), res.end());return res;}vector<bool> solve_simultaneous_equation_(vector<vector<T>> &A , vector<T> &b){Matrix X(A), Y(b);return solve_simultaneous_equation_(X, Y);}vector<bool> solve_simultaneous_equation_(Matrix &A , vector<T> &b){Matrix Y(b);return solve_simultaneous_equation_(A, Y);}vector<bool> solve_simultaneous_equation_(vector<vector<T>> &A , Matrix &b){Matrix X(A);return solve_simultaneous_equation_(X, b);}vector<bool> solve_simultaneous_equation_(Matrix &A , Matrix &b){A.concat_col(b);return solve_simultaneous_equation_(A);}vector<bool> solve_simultaneous_equation_(vector<vector<T>> &A){return solve_simultaneous_equation_(to_matrix(A));}vector<bool> solve_simultaneous_equation_(Matrix &M){int n = M.row_size() , m = M.col_size();rank = sweep_out_(M,true);for(int row = rank ; row < n ; row++) if(M[row][n]) return {};vector<bool> res;res.resize(rank);for(int i = 0 ; i < rank; i++) res[i] = M[i][m];return solution = res;}public:GaussJordan(){}int sweep_out(Matrix &A) { return sweep_out_(A, false); }int sweep_out(Matrix &A, bool is_extended) { return sweep_out_(A, is_extended); }vector<vector<bool>> create_xorbase(Matrix &A, bool sorted = false) { return create_xorbase_(A,sorted); }vector<bool> solve_simultaneous_equation(Matrix &A , Matrix &b) { return solve_simultaneous_equation_(A, b); }vector<bool> solve_simultaneous_equation(Matrix &A , vector<T> &b) { return solve_simultaneous_equation_(A, b); }vector<bool> solve_simultaneous_equation(vector<vector<T>> &A , vector<T> &b) { return solve_simultaneous_equation_(A, b); }vector<bool> solve_simultaneous_equation(vector<vector<T>> &A , Matrix &b) { return solve_simultaneous_equation_(A, b); }vector<bool> solve_simultaneous_equation(vector<vector<T>> &A) { return solve_simultaneous_equation_(A); }vector<bool> solve_simultaneous_equation(Matrix A) { return solve_simultaneous_equation_(A); }int get_rank() { return rank; }vector<T> get_solution() { return solution; }};const int mod = 998244353 ;ll powmod(ll x , ll n){ll res = 1 ;while(n > 0){if(n & 1) (res *= x) %= mod ;(x *= x) %= mod ;n >>= 1 ;}return res ;}int n, m;void solve(){cin >> n >> m;set<ll> st;vector<vector<bool>> A(2*m+1,vector<bool>(n,false));rep(i,m){int k;cin >> k;vector<int> V;rep(j,k) {int a;cin >> a;a--;V.push_back(a);A[i][a] = true;A[i+m][a] = true;st.insert(a);}}rep(i,m){for(int u : st) (A[i+m][u] = A[i+m][u] ? false : true);}rep(i,n) A[2*m][i] = true;Matrix mat(A);GaussJordan gj;int rank = gj.sweep_out(mat);pt(powmod(2,rank))}int main(){fast_ioint t = 1;// cin >> t;rep(i,t) solve();}