結果

問題 No.2895 Zero XOR Subset
コンテスト
ユーザー Today03
提出日時 2024-09-23 05:41:04
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,095 bytes
コンパイル時間 3,656 ms
コンパイル使用メモリ 264,284 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-23 05:41:16
合計ジャッジ時間 11,690 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 WA * 30
権限があれば一括ダウンロードができます

ソースコード

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 のランク
int rowReduction(vector<vector<bool>>& a) {
    int row = a.size(), col = a.front().size();
    int rank = 0;
    for (int c = 0; c < col; c++) {
        if (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 (row != rank && a[r][c]) {
                // A[r]^=A[c]
                for (int i = 0; i < c; i++) a[r][i] = a[r][i] ^ a[rank][i];
            }
        }
        rank++;
    }
    return rank;
}

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

    int rank = rowReduction(a2);

    for (int r = rank; r < row; r++) {
        if (a2[r].back()) return -1;
    }
    if (rank == col && b == vector<bool>(col, false)) return -1;

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

    {
        // いわゆる 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 (int e : a3) {
            for (int 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];
    const int L = 11;

    N = min(N, L);
    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;
        }
    }

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

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

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