結果

問題 No.1421 国勢調査 (Hard)
コンテスト
ユーザー logx
提出日時 2021-01-28 00:09:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,565 bytes
コンパイル時間 1,912 ms
コンパイル使用メモリ 177,676 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-27 03:01:22
合計ジャッジ時間 5,409 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

/*
実行時modint:
template<int &mod>
struct Fp{};
int main(){
    static int mod;cin >> mod;
    using mint = Fp<mod>;
}
*/
template<int mod>
struct Fp{
    long long x;
    constexpr Fp(const long long _x=0)noexcept:x((_x%mod+mod)%mod){}
    constexpr Fp operator-()const noexcept{
        return x ? mod-x:0;
    }
    friend constexpr Fp<mod>& operator+=(Fp<mod> &l,const Fp<mod> r)noexcept{
        l.x+=r.x;
        if(l.x>=mod)l.x-=mod;
        return l;
    }
    friend constexpr Fp<mod>& operator-=(Fp<mod> &l,const Fp<mod> r)noexcept{
        l.x-=r.x;
        if(l.x<0)l.x+=mod;
        return l;
    }
    //modが十分小さい場合
    friend constexpr Fp<mod>& operator*=(Fp<mod> &l,const Fp<mod> r)noexcept{
        l.x=l.x*r.x %mod;
        return l;
    }
    //modが巨大な場合
    /*
    friend constexpr Fp<mod> prod(Fp<mod> l,long long r)noexcept{
        if(r==0)return 0;
        Fp<mod> res=prod(l+=l,r>>1);
        if(r&1)res+=l;
        return res;
    }
    friend constexpr Fp<mod>& operator*=(Fp<mod> &l,const Fp<mod> r)noexcept{
        return l=prod(l,r.x);
    }
    */
    
    friend constexpr Fp<mod>& operator/=(Fp<mod> &l,const Fp<mod> r)noexcept{
        long long a=r.x,b=mod,u=1,v=0;
        while(b){
            ll t=a/b;
            a-=t*b;swap(a,b);
            u-=t*v;swap(u,v);
        }
        l.x=l.x*u%mod;
        if(l.x<0)l.x+=mod;
        return l;
    }
    friend constexpr Fp<mod> operator+(Fp<mod> l,const Fp<mod> r){
        return l+=r;
    }
    friend constexpr Fp<mod> operator-(Fp<mod> l,const Fp<mod> r){
        return l-=r;
    }
    friend constexpr Fp<mod> operator*(Fp<mod> l,const Fp<mod> r){
        return l*=r;
    }
    friend constexpr Fp<mod> operator/(Fp <mod> l,const Fp<mod> r){
        return l/=r;
    }
    #ifdef LOGX
    friend constexpr bool operator==(const Fp<mod> l,const Fp<mod> r){
        return l.x==r.x;
    }
    friend constexpr bool operator!=(const Fp<mod> l,const Fp<mod> r){
        return l.x!=r.x;
    }
    #endif
    friend constexpr ostream& operator<<(ostream &os,const Fp<mod> &r)noexcept{
        return os << r.x;
    }
    friend constexpr istream& operator>>(istream &is,Fp<mod> &r)noexcept{
        ll t=0;is >> t;
        r.x=(Fp<mod>(t)).x;
        return is;
    }
};




template<typename T>
struct Matrix{
    vector<vector<T>> v;
    Matrix(const int n,const int m,T x=0):v(n,vector<T>(m,x)){}
    size_t size()const{return v.size();}
    inline vector<T>& operator[](const int i){return v[i];}
};

template<int MOD>
int modp_Gauss_Jordan(Matrix<Fp<MOD>> &a,bool is_ex=false){
    int m=a.size(),n=a[0].size();
    
    int rank=0;
    for(int col=0;col<n;col++){
        //拡大係数行列を見ているなら一番右について操作しない.
        if(is_ex && col+1==n)break;
        //その列の非零元を探し,その列を上の方へ.なければ次の列へ.
        int piv=-1;
        for(int row=rank;row<m;row++){
            if(a[row][col].x!=0){
                piv=row;
                break;
            }
        }
        if(piv==-1)continue;
        swap(a[piv] , a[rank]);

        //上の方に持ってきた列のピボットが1になるように定数倍.
        Fp<MOD> now=1/a[rank][col];
        for(int col2=col;col2<n;col2++){////////
            a[rank][col2]=a[rank][col2]*now;
        }
        //その列に零でない元があると困るので,それを取り除く.
        //a[rank]の左の方は全て零なので,引き算するところはcol2>=colでよい.
        for(int row=0;row<m;row++){
            if(row!=rank && a[row][col].x!=0){
                Fp<MOD> fac=a[row][col];
                for(int col2=col;col2<n;col2++){
                    a[row][col2]-=a[rank][col2]*fac;
                }
            }
        }
        rank++;
    }
    return rank;
}

//A(res)=bを解く.
template<int MOD>
int modp_linear_equation(Matrix<Fp<MOD>>A,vector<ll> b,vector<ll> &res){
    int m=A.size(),n=A[0].size();
    Matrix<Fp<MOD>> 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=Gauss_Jordan(M,true);
    for(int row=rank;row<m;row++)if(M[row][n].x!=0)return -1;
    res.assign(n,0);
    for(int i=0;i<rank;i++)res[i]=M[i][n].x;
    return rank;
}


const int MAX_COL=51;//適宜.
struct bitMatrix{
    int h,w;
    vector<bitset<MAX_COL>> val;
    bitMatrix(int m=1,int n=1):h(m),w(n){
        val.resize(h);
    }
    inline bitset<MAX_COL>& operator[](const int i){return val[i];}
};
int bit_Gauss_Jordan(bitMatrix &a,bool is_ex=false){
    int rank=0;
    for(int col=0;col<a.w;col++){
        if(is_ex && col+1==a.w)break;
        //その列の非零元を探し,上へ.
        int piv=-1;
        for(int row=rank;row<a.h;row++){
            if(a[row][col]){
                piv=row;
                break;
            }
        }
        if(piv==-1)continue;
        swap(a[piv] , a[rank]);
        //F_2で非零元は1なので,ピボットは必ず1.

        //その列に零でない元があると困るので,それを取り除く.
        //xorが足し算/引き算に相当する.
        for(int row=0;row<a.h;row++){
            if(row!=rank && a[row][col])a[row]^=a[rank];
        }
        rank++;
    }
    return rank;
}

int bit_linear_equation(bitMatrix A,vector<int> b,vector<int> &res){
    int m=A.h;
    int 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=bit_Gauss_Jordan(M,true);
    for(int row=rank;row<m;row++)if(M[row][n])return -1;
    res.assign(n,0);
    for(int i=0;i<rank;i++)res[i]=M[i][n];
    return rank;
}

const int mod=5;
using mat=Matrix<Fp<mod>>;

int main(){
    int N,M;cin >> N >> M;
    bitMatrix B(M,N);
    vector<int> Y(M);
    for(int i=0;i<M;i++){
        int A;cin >> A;
        for(int j=0;j<A;j++){
            int b;cin >> b;
            B[i][b-1]=1;
        }
        cin >> Y[i];
    }

    bool ok=true;
    vector<int> ans(N);
    vector<int> res;
    vector<int> b(M);
    for(int i=0;i<30;i++){
        for(int j=0;j<M;j++)b[j]=((Y[j]>>i)&1);
        int rank=bit_linear_equation(B,b,res);
        if(rank==-1){
            ok=false;
            break;
        }
        for(int j=0;j<N;j++)ans[j]|=(1<<i)*res[j];
    }
    if(!ok)cout << -1 << endl;
    else{
        for(int i=0;i<N;i++)cout << ans[i] << endl;
    }
}
0