#325345 (C++11) No.803 Very Limited Xor Subset

提出ソース

結果

問題	No.803 Very Limited Xor Subset
ユーザー	ゆゆうた
提出日時	2019-03-17 23:56:38
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	12 ms / 2,000 ms
コード長	9,012 bytes
コンパイル時間	1,377 ms
コンパイル使用メモリ	167,304 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-07-08 07:32:56
合計ジャッジ時間	2,834 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	1 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	1 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	8 ms 5,376 KB
testcase_15	AC	9 ms 5,376 KB
testcase_16	AC	8 ms 5,376 KB
testcase_17	AC	8 ms 5,376 KB
testcase_18	AC	9 ms 5,376 KB
testcase_19	AC	8 ms 5,376 KB
testcase_20	AC	9 ms 5,376 KB
testcase_21	AC	8 ms 5,376 KB
testcase_22	AC	8 ms 5,376 KB
testcase_23	AC	12 ms 5,376 KB
testcase_24	AC	10 ms 5,376 KB
testcase_25	AC	11 ms 5,376 KB
testcase_26	AC	11 ms 5,376 KB
testcase_27	AC	11 ms 5,376 KB
testcase_28	AC	11 ms 5,376 KB
testcase_29	AC	11 ms 5,376 KB
testcase_30	AC	11 ms 5,376 KB
testcase_31	AC	11 ms 5,376 KB
testcase_32	AC	11 ms 5,376 KB
testcase_33	AC	11 ms 5,376 KB
testcase_34	AC	2 ms 5,376 KB
testcase_35	AC	10 ms 5,376 KB
testcase_36	AC	4 ms 5,376 KB
testcase_37	AC	5 ms 5,376 KB
testcase_38	AC	2 ms 5,376 KB
testcase_39	AC	2 ms 5,376 KB
testcase_40	AC	11 ms 5,376 KB
testcase_41	AC	10 ms 5,376 KB
testcase_42	AC	10 ms 5,376 KB
testcase_43	AC	10 ms 5,376 KB
testcase_44	AC	2 ms 5,376 KB
testcase_45	AC	2 ms 5,376 KB
testcase_46	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;


template<typename T>
class Vec {
protected:
    using iterator = typename std::vector<T>::iterator;
    using const_iterator = typename std::vector<T>::const_iterator;
    using reference = T &;
    using const_reference = const T &;
    std::vector<T> v;

    template<typename Unop>
    Vec<T> unop_new(Unop op) const {
        Vec<T> res(v.size());
        transform(begin(v), end(v), res.begin(), op);
        return res;
    }

    template<typename Binop>
    Vec<T> &binop(const Vec<T> &r, Binop op) {
        transform(r.begin(), r.end(), v.begin(), v.begin(), op);
        return *this;
    }

    template<typename Binop>
    Vec<T> binop_new(const Vec<T> &r, Binop op) const {
        Vec<T> res(v.size());
        transform(r.begin(), r.end(), v.begin(), res.begin(), op);
        return res;
    }

public:
    Vec(int n) : v(n) {}

    Vec(int n, const T &val) : v(n, val) {}

    Vec(const std::vector<T> &w) : v(w) {}

    int size() const noexcept { return v.size(); }

    const_iterator begin() const noexcept { return v.begin(); }

    const_iterator end() const noexcept { return v.end(); }

    iterator begin() noexcept { return v.begin(); }

    iterator end() noexcept { return v.end(); }

    reference operator[](int i) { return v[i]; }

    const_reference operator[](int i) const { return v[i]; }

    Vec<T> operator-() const {
        return unop_new([](T val) { return -val; });
    };

    Vec<T> &operator+=(const Vec<T> &r) {
        return binop(r, [](T x, T y) { return x + y; });
    }

    Vec<T> &operator-=(const Vec<T> &r) {
        return binop(r, [](T x, T y) { return x - y; });
    }

    Vec<T> operator+(const Vec<T> &r) const {
        return binop_new(r, [](T x, T y) { return x + y; });
    }

    Vec<T> operator-(const Vec<T> &r) const {
        return binop_new(r, [](T x, T y) { return x - y; });
    }

    T dot(const Vec<T> &r) const {
        return inner_product(v.begin(), v.end(), r.begin(), T(0));
    }

    T norm() const { return this->dot(v); }

    void push_back(const T &r) { v.push_back(r); }

    void concat(const Vec<T> &r) { v.insert(v.end(), r.begin(), r.end()); }
};

template<typename T>
class Matrix : public Vec<Vec<T>> {
public:
    using Vec<Vec<T>>::Vec;

    Matrix(int n, int m, const T &val) : Vec<Vec<T>>::Vec(n, Vec<T>(m, val)) {}

    int Y() const { return this->size(); }

    int X() const { return (*this)[0].size(); }

    Matrix<T> transpose() const {
        const int row = Y(), col = X();
        Matrix res(col, row);
        for (int j = 0; j < col; ++j) {
            for (int i = 0; i < row; ++i) {
                res[j][i] = (*this)[i][j];
            }
        }
        return res;
    }

    Matrix<T> operator*(const Matrix<T> &r) const {
        Matrix<T> tr = r.transpose();
        const int row = Y(), col = tr.Y();
        assert(X() == tr.X());
        Matrix<T> res(row, col);
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                res[i][j] = (*this)[i].dot(tr[j]);
            }
        }
        return res;
    }

    Vec<T> operator*(const Vec<T> &r) const {
        const int row = Y(), col = r.Y();
        assert(r.size() == col);
        Vec<T> res(row);
        for (int i = 0; i < row; ++i) {
            res[i] = (*this)[i].dot(r);
        }
        return res;
    }

    Matrix<T> &operator*=(const Matrix<T> &r) { return *this = *this * r; }

    Matrix<T> operator^(ll n) const {
        const int m = Y();
        assert(m == X());
        Matrix<T> A = *this, res(m, m, 0);
        for (int i = 0; i < m; ++i) res[i][i] = 1;
        while (n > 0) {
            if (n % 2) res *= A;
            A = A * A;
            n /= 2;
        }
        return res;
    }

    void concat_right(const Vec<T> &r) {
        const int n = Y();
        assert(n == r.size());
        for (int i = 0; i < n; ++i) {
            (*this)[i].push_back(r[i]);
        }
    }

    void concat_right(const Matrix<T> &r) {
        const int n = Y();
        assert(n == r.Y());
        for (int i = 0; i < n; ++i) {
            (*this)[i].concat(r[i]);
        }
    }

    void concat_below(const Vec<T> &r) {
        assert(Y() == 0 || X() == r.size());
        this->push_back(r);
    }

    void concat_below(const Matrix<T> &r) {
        assert(Y() == 0 || X() == r.X());
        for (Vec<T> i : r) (*this).push_back(i);
    }

    int rank() const {
        Matrix<T> A = *this;
        if (Y() == 0) return 0;
        const int n = Y(), m = X();

        int r = 0;
        for (int i = 0; r < n && i < m; ++i) {
            int pivot = r;
            for (int j = r + 1; j < n; ++j) {
                if (abs(A[j][i]) > abs(A[pivot][i])) pivot = j;
            }
            std::swap(A[pivot], A[r]);
            if (A[r][i] == 0) continue;
            for (int k = m - 1; k >= i; --k) A[r][k] = A[r][k] / A[r][i];
            for (int j = r + 1; j < n; ++j) {
                for (int k = m - 1; k >= i; --k) {
                    A[j][k] ^= A[r][k] * A[j][i];
                }
            }
            ++r;
        }

        for(int i = 0 ; i < n ; i++){
            bool bad = A[i][m-1];
            for(int j = 0 ; j < m-1 ; j++){
                bad = bad & !A[i][j];
            }
            if(bad){
                return -1;
            }
        }

        return r;
    }
};

Vec<int> create(int x) {
    Vec<int> res(30);
    for (int i = 0; i < 30; i++) {
        res[i] = x >> i & 1;
    }
    return res;
}


int A[310];


template<int M, bool IsPrime = false>
class Modulo {
    int n;

    static typename std::enable_if<IsPrime, ll>::type inv(ll a, ll p) {
        return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
    }

public:
    Modulo() : n(0) { ; }

    Modulo(int m) : n(m) {
        if (n >= M)
            n %= M;
        else if (n < 0)
            n = (n % M + M) % M;
    }

    Modulo(ll m) {
        if (m >= M)
            m %= M;
        else if (m < 0)
            m = (m % M + M) % M;
        n = m;
    }

    explicit operator int() const { return n; }

    explicit operator ll() const { return n; }

    bool operator==(const Modulo &a) const { return n == a.n; }

    Modulo &operator+=(const Modulo &a) {
        n += a.n;
        if (n >= M) n -= M;
        return *this;
    }

    Modulo &operator-=(const Modulo &a) {
        n -= a.n;
        if (n < 0) n += M;
        return *this;
    }

    Modulo &operator*=(const Modulo &a) {
        n = (ll(n) * a.n) % M;
        return *this;
    }

    Modulo operator+(const Modulo &a) const {
        Modulo res = *this;
        return res += a;
    }

    Modulo operator-(const Modulo &a) const {
        Modulo res = *this;
        return res -= a;
    }

    Modulo operator-() const { return Modulo(0) - *this; }

    Modulo operator*(const Modulo &a) const {
        Modulo res = *this;
        return res *= a;
    }

    Modulo operator^(ll m) const {
        if (m == 0) return Modulo(1);
        const Modulo a = *this;
        Modulo res = (a * a) ^(m / 2);
        return m % 2 ? res * a : res;
    }

    typename std::enable_if<IsPrime, Modulo>::type
    operator/(const Modulo &a) const {
        return *this * inv(ll(a), M);
    }

    typename std::enable_if<IsPrime, Modulo>::type operator/=(const Modulo &a) {
        return *this *= inv(ll(a), M);
    }

    friend bool is_zero(const Modulo &x) { return int(x) == 0; }

    friend int abs(const Modulo &x) { return int(x); }

    static Modulo fact(int n, bool sw = true) {
        static std::vector<Modulo> v1 = {1}, v2 = {1};
        if (n >= (int) v1.size()) {
            const int from = v1.size(), to = n + 1024;
            v1.reserve(to);
            v2.reserve(to);
            for (int i = from; i < to; ++i) {
                v1.push_back(v1.back() * Modulo<M, true>(i));
                v2.push_back(v2.back() / Modulo<M, true>(i));
            }
        }
        return sw ? v1[n] : v2[n];
    }

    static Modulo comb(int a, int b) {
        if (b < 0 || b > a) return 0;
        return Modulo::fact(a, true) * Modulo::fact(b, false) *
               Modulo::fact(a - b, false);
    }
};

typedef Modulo<1000000007, true> mInt;

int main() {
    int N, M, X;
    cin >> N >> M >> X;
    auto xv = create(X);

    for (int i = 0; i < N; i++) cin >> A[i];
    Matrix<int> mat1(30 + M, N + 1);

    for (int j = 0; j < 30; j++) {
        mat1[j][N] = xv[j];
    }

    for (int i = 0; i < N; i++) {
        auto r = create(A[i]);
        for (int j = 0; j < 30; j++) {
            mat1[j][i] = r[j];
        }
    }

    for (int i = 30; i < 30 + M; i++) {
        int t, a, b;
        cin >> t >> a >> b;
        --a;
        for (int j = a; j < b; j++) {
            mat1[i][j] = 1;
        }
        mat1[i][N] = t;
    }

    int r = mat1.rank();
    if(r == -1 ){
        cout << 0 << endl;
        return 0;
    }
    mInt ans = mInt(2) ^ (N - r);
    cout << (int) ans << endl;
}

yukicoder

結果

テストケース

ソースコード