test/src/linear_algebra/xor_base/AOJ_3277.test.cpp

• View this file on GitHub
• Last update: 2022-07-10 17:12:10+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3277

Depends on

• XOR 基底 (library/linear_algebra/xor_base.hpp)

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3277"

#include <iostream>

#include "library/linear_algebra/xor_base.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int k;
    std::cin >> k;

    std::vector<int> siz(k);
    for (auto& e : siz) std::cin >> e;

    std::vector<suisen::XorBase<uint64_t>> dp(1 << k);
    for (int i = 0; i < 60; ++i) {
        dp[0] += uint64_t(1) << i;
    }
    for (int i = 0; i < k; ++i) {
        suisen::XorBase<uint64_t> b;
        for (int j = 0; j < siz[i]; ++j) {
            uint64_t v;
            std::cin >> v;
            b += v;
        }
        dp[1 << i] = b;
    }

    uint64_t ans = 0;
    for (int s = 1; s < 1 << k; ++s) {
        int pc = __builtin_popcount(s);
        if (pc > 1) {
            int l = s & -s, t = s ^ l;
            dp[s] = dp[t] & dp[l];
        }
        if (pc & 1) {
            ans += uint64_t(1) << dp[s].dim();
        } else {
            ans -= uint64_t(1) << dp[s].dim();
        }
    }
    std::cout << ans << std::endl;

    return 0;
}

#line 1 "test/src/linear_algebra/xor_base/AOJ_3277.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3277"

#include <iostream>

#line 1 "library/linear_algebra/xor_base.hpp"



#include <vector>

namespace suisen {
    template <typename T>
    struct XorBase {
        XorBase() = default;
        XorBase(const std::vector<T> &a) : XorBase() {
            for (const auto &v : a) add(v);
        }

        bool add(T v) {
            for (const auto &e : _basis) if (T w = e ^ v; w < v) v = std::move(w);
            return v ? (_basis.push_back(v), true) : false;
        }
        XorBase<T>& operator+=(const XorBase<T> &rhs) {
            for (const T &e : rhs._basis) add(e);
            return *this;
        }
        XorBase<T>& operator+=(const T &v) {
            add(v);
            return *this;
        }
        XorBase<T> operator+(const XorBase<T> &rhs) const {
            XorBase<T> res;
            res._basis = _basis;
            return res += rhs;
        }
        XorBase<T> operator+(const T &v) const {
            return *this + XorBase<T>({ v });
        }

        XorBase<T> intersection(const XorBase<T> &rhs) const {
            std::vector<std::pair<T, T>> basis;
            for (const T &e : _basis) basis.emplace_back(e, e);
            XorBase<T> res;
            for (T e : rhs._basis) {
                T s;
                if constexpr (std::is_integral_v<T>) s = 0;
                for (const auto &[v, t] : basis) if (T w = e ^ v; w < e) e = std::move(w), s ^= t;
                if (e) basis.emplace_back(e, s);
                else res.add(s);
            }
            return res;
        }
        XorBase<T>& operator&=(const XorBase<T> &rhs) {
            return *this = intersection(rhs);
        }
        XorBase<T> operator&(const XorBase<T> &rhs) const {
            return intersection(rhs);
        }

        int dim() const { return _basis.size(); }

        const std::vector<T>& get_basis() const { return _basis; }
    private:
        std::vector<T> _basis;
    };
} // namespace suisen



#line 6 "test/src/linear_algebra/xor_base/AOJ_3277.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int k;
    std::cin >> k;

    std::vector<int> siz(k);
    for (auto& e : siz) std::cin >> e;

    std::vector<suisen::XorBase<uint64_t>> dp(1 << k);
    for (int i = 0; i < 60; ++i) {
        dp[0] += uint64_t(1) << i;
    }
    for (int i = 0; i < k; ++i) {
        suisen::XorBase<uint64_t> b;
        for (int j = 0; j < siz[i]; ++j) {
            uint64_t v;
            std::cin >> v;
            b += v;
        }
        dp[1 << i] = b;
    }

    uint64_t ans = 0;
    for (int s = 1; s < 1 << k; ++s) {
        int pc = __builtin_popcount(s);
        if (pc > 1) {
            int l = s & -s, t = s ^ l;
            dp[s] = dp[t] & dp[l];
        }
        if (pc & 1) {
            ans += uint64_t(1) << dp[s].dim();
        } else {
            ans -= uint64_t(1) << dp[s].dim();
        }
    }
    std::cout << ans << std::endl;

    return 0;
}

Back to top page