Test/DataStructure/Accumulation_xor.test.cpp

View this file on GitHub
Last update: 2024-12-27 16:29:20+09:00
Problem: https://yukicoder.me/problems/no/1456

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/1456"

#include <iostream>

#include <unordered_set>


// begin:tag includes

#include "./../../Library/DataStructure/Accumulation.hpp"

// end:tag includes


using ll = long long;

signed main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

  ll n, k;
  std::cin >> n >> k;

  std::vector<ll> a;
  a.reserve(n);
  for (int _ = 0; _ < n; ++_) {
    ll x;
    std::cin >> x;
    a.emplace_back(x);
  }

  auto inv = [](ll x) { return x; };
  auto op = [](ll x, ll y) { return x ^ y; };
  using G = mtd::Group<ll, 0, decltype(op), decltype(inv)>;
  auto acc = mtd::Accumulation<G>(a);

  std::unordered_set<ll> st;
  for (int i = 0; i < n; ++i) { st.emplace(acc.get(i) ^ k); }

  if (st.find(0) != st.end()) {
    std::cout << "Yes" << std::endl;
    return 0;
  }
  for (int i = 0; i < n; ++i) {
    if (st.find(acc.get(i)) != st.end()) {
      std::cout << "Yes" << std::endl;
      return 0;
    }
  }
  std::cout << "No" << std::endl;
}

#line 1 "Test/DataStructure/Accumulation_xor.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1456"

#include <iostream>

#include <unordered_set>


// begin:tag includes

#line 2 "Library/DataStructure/Accumulation.hpp"

#include <algorithm>

#include <vector>


#line 2 "Library/Algebraic/Group.hpp"

#line 4 "Library/Algebraic/Group.hpp"

namespace mtd {

  template <class S,    // set
            S element,  // identity element
            class op,   // binary operation
            class inv   // inverse operation
            >
  requires std::is_invocable_r_v<S, op, S, S>
  struct Group {
    using value_type = S;
    constexpr static S _element = element;
    using op_type = op;
    using inv_type = inv;

    S m_val;
    constexpr Group() : m_val(element) {}
    constexpr Group(S val) : m_val(val) {}
    constexpr Group inverse() const { return inv()(m_val); }
    constexpr Group binaryOperation(const Group& g) const {
      return op()(m_val, g.m_val);
    }
    constexpr friend std::ostream& operator<<(
        std::ostream& os, const Group<S, element, op, inv>& g) {
      return os << g.m_val;
    }
  };

  namespace __detail {
    template <typename T,
              template <typename, auto, typename, typename> typename S>
    concept is_group_specialization_of = requires {
      typename std::enable_if_t<
          std::is_same_v<T, S<typename T::value_type, T::_element,
                              typename T::op_type, typename T::inv_type>>>;
    };
  }  // namespace __detail

  template <typename G>
  concept group = __detail::is_group_specialization_of<G, Group>;

}  // namespace mtd
#line 7 "Library/DataStructure/Accumulation.hpp"

namespace mtd {

  namespace type {

    using inv = decltype([](auto x) { return -x; });
    using op = decltype([](auto x, auto y) { return x + y; });
    template <class P>
    using AdditiveGroup = Group<P, P(0), op, inv>;

  }  // namespace type


  template <group Group = type::AdditiveGroup<long long>>
  class Accumulation {
    using S = decltype(Group().m_val);

    const int size;
    std::vector<Group> sumList;

  public:
    constexpr Accumulation() = delete;
    constexpr Accumulation(const std::vector<Group>& v)
        : size(v.size()), sumList(size + 1) {
      for (int i = 0; i < size; ++i) {
        sumList[i + 1] = sumList[i].binaryOperation(v[i]);
      }
    }
    constexpr Accumulation(const std::vector<S>& v)
        : Accumulation(std::vector<Group>(v.begin(), v.end())) {}

    constexpr auto get(int n) const { return sumList[n + 1].m_val; }
    constexpr auto get(int l, int r) const {
      if (r < l) { return Group::_element; }
      l = std::max(l, 0);
      r = std::min(r, size - 1);
      return sumList[r + 1].binaryOperation(sumList[l].inverse()).m_val;
    }

    constexpr friend std::ostream& operator<<(std::ostream& os,
                                              const Accumulation<Group>& acc) {
      for (const auto& x : acc.sumList) { os << x << " "; }
      return os;
    }
  };

}  // namespace mtd

#line 8 "Test/DataStructure/Accumulation_xor.test.cpp"
// end:tag includes


using ll = long long;

signed main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

  ll n, k;
  std::cin >> n >> k;

  std::vector<ll> a;
  a.reserve(n);
  for (int _ = 0; _ < n; ++_) {
    ll x;
    std::cin >> x;
    a.emplace_back(x);
  }

  auto inv = [](ll x) { return x; };
  auto op = [](ll x, ll y) { return x ^ y; };
  using G = mtd::Group<ll, 0, decltype(op), decltype(inv)>;
  auto acc = mtd::Accumulation<G>(a);

  std::unordered_set<ll> st;
  for (int i = 0; i < n; ++i) { st.emplace(acc.get(i) ^ k); }

  if (st.find(0) != st.end()) {
    std::cout << "Yes" << std::endl;
    return 0;
  }
  for (int i = 0; i < n; ++i) {
    if (st.find(acc.get(i)) != st.end()) {
      std::cout << "Yes" << std::endl;
      return 0;
    }
  }
  std::cout << "No" << std::endl;
}