結果

問題 No.803 Very Limited Xor Subset
ユーザー tsutajtsutaj
提出日時 2019-07-11 17:06:48
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 5,016 bytes
コンパイル時間 870 ms
コンパイル使用メモリ 81,420 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-07 18:24:01
合計ジャッジ時間 2,512 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 3 ms
4,380 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 2 ms
4,376 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 2 ms
4,380 KB
testcase_23 AC 2 ms
4,380 KB
testcase_24 AC 3 ms
4,376 KB
testcase_25 AC 3 ms
4,380 KB
testcase_26 AC 2 ms
4,376 KB
testcase_27 AC 2 ms
4,376 KB
testcase_28 AC 2 ms
4,376 KB
testcase_29 AC 3 ms
4,380 KB
testcase_30 AC 2 ms
4,376 KB
testcase_31 AC 2 ms
4,376 KB
testcase_32 AC 2 ms
4,376 KB
testcase_33 AC 2 ms
4,380 KB
testcase_34 AC 2 ms
4,376 KB
testcase_35 AC 2 ms
4,380 KB
testcase_36 AC 2 ms
4,380 KB
testcase_37 AC 2 ms
4,376 KB
testcase_38 AC 2 ms
4,380 KB
testcase_39 AC 2 ms
4,376 KB
testcase_40 AC 2 ms
4,380 KB
testcase_41 AC 2 ms
4,376 KB
testcase_42 AC 2 ms
4,380 KB
testcase_43 AC 2 ms
4,376 KB
testcase_44 AC 1 ms
4,376 KB
testcase_45 AC 1 ms
4,376 KB
testcase_46 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <bitset>
#include <algorithm>
#include <iostream>
#include <cassert>
using namespace std;

// mod2 行列ライブラリ (bitset を使って高速化、横は SIZE 固定とする)
struct BinaryMatrix {
    int H, W;
    static const int SIZE = 2010;
    vector< bitset<SIZE> > mat;
    BinaryMatrix(int H_, int W_) : H(H_), W(W_), mat(H_) {}

    // 乗算に使用 (これ微妙に転置じゃないけどなんていうんだ)
    BinaryMatrix T(const BinaryMatrix& A) {
        int h = A.H, w = A.W;
        BinaryMatrix res(w, h);
        for(int i=0; i<h; i++) {
            for(int j=0; j<w; j++) {
                res[j][i] = A[i][j];
            }
        }
        return res;
    }

    BinaryMatrix& operator*=(const BinaryMatrix& rhs) {
        assert(W == rhs.H);
        BinaryMatrix res(H, rhs.W), trhs = T(rhs);
        for(int i=0; i<H; i++) {
            for(int j=0; j<rhs.W; j++) {
                res[i][j] = (mat[i] & trhs[j]).count() % 2;
            }
        }
        return (*this = res);
    }
    BinaryMatrix& operator+=(const BinaryMatrix &rhs) {
        assert(H == rhs.H and W == rhs.W);
        for(int i=0; i<H; i++) mat[i] ^= rhs[i];
        return *this;
    }
    BinaryMatrix& operator-=(const BinaryMatrix &rhs) {
        return (*this += rhs);
    }

    BinaryMatrix operator*(const BinaryMatrix &rhs) {
        return (BinaryMatrix(*this) *= rhs);
    }
    BinaryMatrix operator+(const BinaryMatrix &rhs) {
        return (BinaryMatrix(*this) += rhs);
    }
    BinaryMatrix operator-(const BinaryMatrix &rhs) {
        return (BinaryMatrix(*this) -= rhs);
    }

    bool operator==(const BinaryMatrix &rhs) const {
        if(H != rhs.H or W != rhs.W) return false;
        for(int i=0; i<H; i++) if(mat[i] != rhs[i]) return false;
        return true;
    }
    bool operator!=(const BinaryMatrix &rhs) const {
        return !(*this == rhs);
    }

    const bitset<SIZE>& operator[](int k) const { return mat[k]; }
    bitset<SIZE>& operator[](int k) { return mat[k]; }
};

BinaryMatrix eigen(size_t N) {
    BinaryMatrix res(N, N);
    for(size_t i=0; i<N; i++) res[i][i] = 1;
    return res;
}

BinaryMatrix pow(BinaryMatrix mat, long long int k) {
    BinaryMatrix res = eigen(mat.H);
    for(; k>0; k>>=1) {
        if(k & 1) res *= mat;
        mat *= mat;
    }
    return res;
}

int gaussianEliminationBinary(BinaryMatrix &mat, bool ext=false) {
    int N = mat.H, M = mat.W, rank = 0;
    for(int j=0; j+ext<M; j++) {
        int piv = -1;
        for(int i=rank; i<N; i++) {
            if(mat[i][j] != 0) piv = i, i = N;
        }
        if(piv < 0) continue;
        swap(mat[rank], mat[piv]);
        for(int i=0; i<N; i++) {
            if(i == rank or mat[i][j] == 0) continue;
            mat[i] ^= mat[rank];
        }
        rank++;
    }
    return rank;
}

vector<int> linearEquationBinary(BinaryMatrix A, vector<int> b) {
    int N = A.H, M = A.W;
    BinaryMatrix mat(N, M+1);
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            mat[i][j] = (j < M ? A[i][j] : b[i]);
        }
    }

    int rank = gaussianEliminationBinary(mat, true);
    vector<int> res(N);
    for(int i=0; i<N; i++) {
        res[i] = mat[i][M];
        if(i >= rank and mat[i][M] == 0) return {};
    }
    return res;
}

int detBinary(BinaryMatrix A) {
    int N = A.H;
    for(int j=0; j<N; j++) {
        int piv = -1;
        for(int i=j; i<N; i++) {
            if(A[i][j] != 0) piv = i, i = N;
        }
        if(piv < 0) return 0;
        swap(A[piv], A[j]);
        for(int i=j+1; i<N; i++) {
            if(A[i][j]) A[i] ^= A[j];
        }
    }
    int res = 1;
    for(int i=0; i<N; i++) res *= A[i][i];
    return res;
}


void ARC054_C() {
    int N; cin >> N;
    BinaryMatrix mat(N, N);
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            char c; cin >> c;
            if(c == '1') mat[i][j] = 1;
        }
    }

    int d = detBinary(mat);
    if(d == 0) cout << "Even" << endl;
    else cout << "Odd" << endl;
}

void yuki_803() {
    const int B = 30;
    int N, M, X; cin >> N >> M >> X;
    BinaryMatrix mat(B+M, N+1);

    for(int j=0; j<B; j++) {
        int p = X & 1;
        mat[j][N] = p;
        X >>= 1;
    }

    for(int i=0; i<N; i++) {
        int val; cin >> val;
        for(int j=0; j<B; j++) {
            int p = val & 1;
            mat[j][i] = p;
            val >>= 1;
        }
    }

    for(int i=0; i<M; i++) {
        int t, l, r; cin >> t >> l >> r; l--;
        mat[B+i][N] = t;
        for(int x=l; x<r; x++) mat[B+i][x] = 1;
    }

    int rank = gaussianEliminationBinary(mat, true);
    for(int i=rank; i<B+M; i++) {
        if(mat[i][N] != 0) {
            cout << 0 << endl;
            return;
        }
    }

    int p = N - rank, ans = 1, MOD = 1000000007;
    for(int i=0; i<p; i++) (ans *= 2) %= MOD;
    cout << ans << endl;
}

int main() {
    // ARC054_C(); // detBinary
    yuki_803(); // gaussianEliminationBinary
    return 0;
}
0