結果

問題 No.2895 Zero XOR Subset
ユーザー Today03Today03
提出日時 2024-09-21 20:00:22
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,040 bytes
コンパイル時間 3,378 ms
コンパイル使用メモリ 261,784 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-21 20:00:33
合計ジャッジ時間 10,102 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

/*
    ガウスの消去法によって、F_2 上の連立線形方程式 Ax = 0 を解く。
    計算量: O(n^3)
    戻り値: 解が存在するかどうか
    x0: 特殊解
    xs: 解空間の基底
*/

int gaussJordan(vector<vector<bool>> &a, bool extended = false) {
    int rank = 0;
    int row = a.size(), col = a[0].size();
    for (int c = 0; c < col; c++) {
        if (extended && c == col - 1) break;
        int pivot = -1;
        for (int r = rank; r < row; r++) {
            if (a[r][c]) {
                pivot = r;
                break;
            }
        }
        if (pivot == -1) continue;
        swap(a[pivot], a[rank]);
        for (int r = 0; r < row; r++) {
            if (r == rank) continue;
            if (a[r][c]) {
                for (int cc = 0; cc < col; cc++) {
                    a[r][cc] = a[r][cc] ^ a[rank][cc];
                }
            }
        }
        rank++;
    }
    return rank;
}

bool solveLinearEquation(vector<vector<bool>> a, vector<bool> b, vector<bool> &x0, vector<vector<bool>> &xs) {
    int row = a.size(), col = a[0].size();
    // a を拡大係数行列にする
    for (int i = 0; i < row; i++) a[i].push_back(b[i]);
    int rank = gaussJordan(a, true);
    // 解が存在するかどうか
    for (int i = 0; i < row; i++) {
        if (a[i][col]) return false;
    }
    // 特殊解（自由変数を全て 0 とする）
    x0 = vector<bool>(col);
    for (int i = 0; i < rank; i++) x0[i] = a[i][col];
    // ker(A) の基底
    xs = vector<vector<bool>>(col - rank, vector<bool>(col));
    {
        vector<ll> basis, a2(row);
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) a2[i] |= (ll)a[i][j] << j;
        }
        for (ll v : a2) {
            for (ll w : basis) {
                v = min(v, v ^ w);
            }
            if (v) basis.push_back(v);
        }
        // assert((int)basis.size()==col-rank);
        for (int i = 0; i < col - rank; i++) {
            for (int j = 0; j < col; j++) {
                xs[i][j] = (basis[i] >> j) & 1;
            }
        }
    }
    return true;
}

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    N = min(N, 60);
    vector<vector<bool>> a(60, vector<bool>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 60; j++) {
            a[j][i] = (A[i] >> j) & 1;
        }
    }

    vector<bool> x0;
    vector<vector<bool>> xs;

    if (solveLinearEquation(a, vector<bool>(N), x0, xs) && xs.size() > 0) {
        vector<int> ans;
        for (int i = 0; i < N; i++) {
            if (xs[0][i]) {
                ans.push_back(i);
            }
        }

        assert(ans.size() > 0);

        cout << ans.size() << endl;
        for (int x : ans) {
            cout << x + 1 << ' ';
        }
        cout << endl;
    } else {
        cout << -1 << endl;
    }
}
0