結果

問題 No.1421 国勢調査 (Hard)
ユーザー logxlogx
提出日時 2021-01-28 00:06:16
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 6,563 bytes
コンパイル時間 2,512 ms
コンパイル使用メモリ 205,968 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-09 09:52:50
合計ジャッジ時間 8,038 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 2 ms
4,376 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 2 ms
4,380 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 1 ms
4,376 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 WA -
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 2 ms
4,376 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
権限があれば一括ダウンロードができます

ソースコード

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_ROW=510;
const int MAX_COL=510;//適宜.
struct bitMatrix{
    int h,w;
    bitset<MAX_COL> val[MAX_ROW];
    bitMatrix(int m=1,int n=1):h(m),w(n){}
    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