結果

問題 No.2895 Zero XOR Subset
コンテスト
ユーザー Today03
提出日時 2025-08-10 16:18:18
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 106 ms / 2,000 ms
コード長 3,734 bytes
コンパイル時間 4,132 ms
コンパイル使用メモリ 290,952 KB
実行使用メモリ 9,216 KB
最終ジャッジ日時 2025-08-10 16:18:27
合計ジャッジ時間 6,676 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for(ll i=0; i<(ll)(n); i++)

template<typename T> bool chmax(T& a, T b) { return a<b ? a=b, true : false; }
template<typename T> bool chmin(T& a, T b) { return a>b ? a=b, true : false; }
using ll=long long; const int INF=1e9+10; const ll INFL=4e18;
using VI=vector<int>; using VVI=vector<VI>; using VL=vector<ll>; using VVL=vector<VL>;
using PL=pair<ll,ll>; using VP=vector<PL>; using WG=vector<vector<pair<int,ll>>>;

#ifdef LOCAL
#include "./debug.hpp"
#else
#define debug(...)
#define print_line
#endif



/// @brief F_2 上の連立線形方程式
/// @ref https://mathlandscape.com/solution-sp/
/// @ref https://yukicoder.me/submissions/1011997
/// @ref verify: https://yukicoder.me/problems/no/2895

/// @brief 掃き出し法
/// @param a 連立方程式 Ax=b の拡大係数行列
/// @param col 拡大係数行列の列数
/// @param where ピボットとなる変数を記録するための配列
/// @return A のランク
template<int MAX_COL>
int RowReduction(vector<bitset<MAX_COL>>& a, int col, vector<int>& where) {
    int row=a.size();
    int rank=0;
    for(int c=0; c<col-1; c++) {
        int pivot=rank;
        while(pivot<row && !a[pivot][c]) pivot++;
        if(pivot==row) continue;
        swap(a[pivot],a[rank]);
        where.push_back(c);
        for(int r=0; r<row; r++) {
            if(r!=rank && a[r][c]) a[r]^=a[rank];
        }
        rank++;
    }
    return rank;
}

/// @brief 連立線形方程式 Ax=b を解く
/// @param col 連立方程式の変数の数
/// @param x0 特殊解(b=0 の場合は自明解になる)
/// @param ker Ax=0 の解空間の基底
/// @param ONE_KER 基底のサイズが巨大な場合、基底を1つだけ求められれば良いときはtrue
/// @note 一般解は x0 と解空間の基底の任意の線形結合で表される
/// @attention A のサイズによっては基底のサイズが巨大になるので注意すること
template<int MAX_COL, bool ONE_KER=false>
int LinearEquation(vector<bitset<MAX_COL>> a, vector<bool> b, int col, vector<bool>& x0, vector<vector<bool>>& ker) {
    int row=a.size();
    assert(b.size()==row);

    vector<bitset<MAX_COL>> a2(row);
    for(int i=0; i<row; i++) {
        a2[i].reset();
        for(int j=0; j<col; j++) a2[i][j]=a[i][j];
        if(b[i]) a2[i][col]=true;
    }

    vector<int> where;
    int rank=RowReduction<MAX_COL>(a2,col+1,where);

    for(int r=rank; r<row; r++) if(a2[r][col]) return false;

    x0=vector<bool>(col,false);
    for(int i=0; i<rank; i++) x0[where[i]]=a2[i][col];

    int r=0;
    for(int c=0; c<col; c++) {
        if(r<rank && c==where[r]) {
            r++;
            continue;
        }
        vector<bool> x(col);
        x[c]=true;
        for(int r2=0; r2<r; r2++) x[where[r2]]=a2[r2][c];
        ker.push_back(x);

        if (ONE_KER) return true;
    }

    return true;
}

//----------------------------------------------------------

void solve() {
    ll N; cin>>N;
    VL A(N); REP(i,N) cin>>A[i];

    const ll L=60;
    const ll MX=2e5+10;

    vector<bitset<MX>> M(L,bitset<MX>());
    REP(i,N) REP(j,L) M[j][i]=((A[i]>>j)&1);

    vector<bool> x0;
    vector<vector<bool>> ker;
    vector<bool> B(L,false);

    bool res=LinearEquation<MX,true>(M,B,N,x0,ker);
    debug(res,ker);
    if(!res || ker.size()==0) {
        cout<<-1<<endl;
        return;
    }

    VL ans;
    REP(i,N) if(ker[0][i]) ans.push_back(i+1);

    cout<<ans.size()<<endl;
    for(ll x: ans) cout<<x<<' '; cout<<endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cout<<fixed<<setprecision(15);
    int T=1;
    //cin>>T;
    while(T--) solve();
}
0