#926428 (C++17) No.2134 $\sigma$-algebra over Finite Set

提出ソース
結果

問題	No.2134 $\sigma$-algebra over Finite Set
ユーザー	asaringo
提出日時	2023-11-05 10:05:15
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	11,657 bytes
コンパイル時間	2,417 ms
コンパイル使用メモリ	222,204 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-09-25 22:23:32
合計ジャッジ時間	3,786 ms
ジャッジサーバーID （参考情報）	judge5 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	139 ms 5,376 KB
testcase_02	AC	136 ms 5,376 KB
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	AC	5 ms 5,376 KB
testcase_07	AC	6 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	1 ms 5,376 KB
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	AC	57 ms 5,376 KB
testcase_14	WA	-
testcase_15	AC	12 ms 5,376 KB
testcase_16	WA	-
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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()?" ":"");}return os;}
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()?" ":"");}return os;}
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(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;
            st.insert(a);
        }
    }
    rep(u,n) A[m][u] = true;
    Matrix mat(A);
    GaussJordan gj;
    int rank = gj.sweep_out(mat);
    pt(powmod(2,rank))
}

int main(){
    fast_io
    int t = 1;
    // cin >> t;
    rep(i,t) solve();
}
yukicoder

結果

テストケース

ソースコード
