結果

問題 No.2895 Zero XOR Subset
コンテスト
ユーザー Today03
提出日時 2024-09-23 06:51:55
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 4,014 bytes
コンパイル時間 3,550 ms
コンパイル使用メモリ 260,716 KB
実行使用メモリ 814,796 KB
最終ジャッジ日時 2024-09-23 06:52:02
合計ジャッジ時間 6,464 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 MLE * 1
other -- * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9 + 10;
const ll INFL = 4e18;

/*
    F_2 上の連立線形方程式
    ref: https://qiita.com/drken/items/a14e9af0ca2d857b85c3
*/

// 掃き出し法
// vector<vector<bool>> a: 連立方程式 Ax=b の拡大係数行列
// return: a のランク

template <int Row, int Col>
struct BitMatrix {
    int row, col;
    array<bitset<Col>, Row> val;
    BitMatrix() {
        row = Row;
        col = Col;
        for (int i = 0; i < row; i++) val[i].reset();
    }
};

template <int row, int col>
int rowReduction(BitMatrix<row, col>& a, vector<int>& where) {
    int rank = 0;
    for (int c = 0; c < col - 1; c++) {
        int pivot = rank;
        while (pivot < row && !a.val[pivot][c]) pivot++;
        if (pivot == row) continue;
        swap(a.val[pivot], a.val[rank]);
        where.push_back(c);
        for (int r = 0; r < row; r++) {
            if (r != rank && a.val[r][c]) {
                for (int i = 0; i < c; i++) a.val[r][i] = a.val[r][i] ^ a.val[rank][i];
            }
        }
        rank++;
        if (rank == row) break;
    }
    return rank;
}

// 連立線形方程式 Ax=b を解く
// x0: 特殊解(b=0 の場合は自明解になる)
// ker: Ax=0 の解空間の基底
// 一般解は x0 と解空間の基底の任意の線形結合で表される
template <int row, int col>
bool linearEquation(BitMatrix<row, col> a, BitMatrix<col, 1> b, vector<bool>& x0, vector<vector<bool>>& ker) {
    BitMatrix<row, col + 1> a2;
    for (int r = 0; r < row; r++) {
        for (int c = 0; c < col; c++) a2.val[r][c] = a.val[r][c];
        a2.val[r][col] = b.val[r][0];
    }

    vector<int> where;
    int rank = rowReduction(a2, where);

    for (int r = rank; r < row; r++) {
        if (a2.val[r][col]) return false;
    }
    if (!where.empty() && where.back() == col) return false;

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

    // Ax=0 の解空間の基底
    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.val[r2][c];
        ker.push_back(x);
    }
    /*{
        //いわゆる noshi 基底
        vector<ll>a3(row);
        for(int r=0;r<row;r++){
            for(int c=0;c<col;c++)a3[r]|=(ll)a[r][c]<<c;
        }
        vector<ll>basis;
        for(ll e:a3){
            for(ll b:basis)e=min(e,e^b);
            if(e)basis.push_back(e);
        }

        ker=vector<vector<bool>>(basis.size(),vector<bool>(col,false));
        for(int r=0;r<(int)basis.size();r++){
            for(int c=0;c<col;c++)ker[r][c]=basis[r]>>c&1;
        }
    }*/

    return rank;
}

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) {
        if (A[i] == 0) {
            cout << 1 << endl;
            cout << i + 1 << endl;
            return 0;
        }
    }
    const int L = 60;

    /*vector<vector<bool>> a(L, vector<bool>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < L; j++) {
            a[j][i] = (A[i] >> j) & 1;
        }
    }*/
    BitMatrix<L, 200000> a;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < L; j++) {
            // a(j,i)=(A[i]>>j)&1;
            a.val[j][i] = (A[i] >> j) & 1;
        }
    }

    vector<bool> x0;
    vector<vector<bool>> xs;
    BitMatrix<200000, 1> b;
    for (int i = 0; i < N; i++) b.val[i][0] = 0;

    bool res = linearEquation<L, 200000>(a, b, x0, xs);
    if (!res || xs.size() == 0) return cout << -1 << endl, 0;

    vector<int> ans;
    for (int i = 0; i < N; i++) {
        if (xs[0][i]) ans.push_back(i + 1);
    }

    if (ans.size() == 0) return cout << -1 << endl, 0;

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