結果
問題 |
No.2895 Zero XOR Subset
|
ユーザー |
![]() |
提出日時 | 2025-08-10 16:08:47 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,630 bytes |
コンパイル時間 | 3,026 ms |
コンパイル使用メモリ | 294,416 KB |
実行使用メモリ | 9,216 KB |
最終ジャッジ日時 | 2025-08-10 16:08:57 |
合計ジャッジ時間 | 8,526 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 WA * 15 |
ソースコード
#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 の解空間の基底 /// @note 一般解は x0 と解空間の基底の任意の線形結合で表される /// @attention A のサイズによっては基底のサイズが巨大になるので注意すること template<int MAX_COL> 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); } 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>(M,B,L,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); if(ans.size()==0) { cout<<-1<<endl; return; } 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(); }