掃き出し法(復元付き)
(math/sweep-restore.hpp)

• View this file on GitHub
• Last update: 2023-05-26 23:34:57+09:00
• Include: #include "math/sweep-restore.hpp"

Required by

• Nimber <-> 多項式環 (math/nimber-to-field.hpp)

Verified with

• verify/verify-unit-test/nimber-to-field.test.cpp

Code

#pragma once

template <typename T>
struct Sweep {
  using P = pair<T, unordered_set<int>>;
  vector<P> basis;

  Sweep() {}
  Sweep(const vector<T>& v) {
    for (int i = 0; i < (int)v.size(); i++) add(v[i], i);
  }

  // x を id と共に追加
  void add(T x, int id) {
    P v{x, {id}};
    for (P& b : basis) {
      if (v.first > (v.first ^ b.first)) apply(v, b);
    }
    if (v.first != T{}) basis.push_back(v);
  }

  // pair(x を復元できるか？, {復元した時の ID の集合})
  pair<bool, vector<int>> restore(T x) {
    P v{x, {}};
    for (P& b : basis) {
      if (v.first > (v.first ^ b.first)) apply(v, b);
    }
    if (v.first != T{}) return {false, {}};
    vector<int> res;
    for (auto& n : v.second) res.push_back(n);
    sort(begin(res), end(res));
    return {true, res};
  }

 private:
  void apply(P& p, const P& o) {
    p.first ^= o.first;
    for (auto& x : o.second) apply(p.second, x);
  }
  void apply(unordered_set<int>& s, int x) {
    if (s.count(x)) {
      s.erase(x);
    } else {
      s.insert(x);
    }
  }
};

/**
 * @brief 掃き出し法(復元付き)
 */

#line 2 "math/sweep-restore.hpp"

template <typename T>
struct Sweep {
  using P = pair<T, unordered_set<int>>;
  vector<P> basis;

  Sweep() {}
  Sweep(const vector<T>& v) {
    for (int i = 0; i < (int)v.size(); i++) add(v[i], i);
  }

  // x を id と共に追加
  void add(T x, int id) {
    P v{x, {id}};
    for (P& b : basis) {
      if (v.first > (v.first ^ b.first)) apply(v, b);
    }
    if (v.first != T{}) basis.push_back(v);
  }

  // pair(x を復元できるか？, {復元した時の ID の集合})
  pair<bool, vector<int>> restore(T x) {
    P v{x, {}};
    for (P& b : basis) {
      if (v.first > (v.first ^ b.first)) apply(v, b);
    }
    if (v.first != T{}) return {false, {}};
    vector<int> res;
    for (auto& n : v.second) res.push_back(n);
    sort(begin(res), end(res));
    return {true, res};
  }

 private:
  void apply(P& p, const P& o) {
    p.first ^= o.first;
    for (auto& x : o.second) apply(p.second, x);
  }
  void apply(unordered_set<int>& s, int x) {
    if (s.count(x)) {
      s.erase(x);
    } else {
      s.insert(x);
    }
  }
};

/**
 * @brief 掃き出し法(復元付き)
 */

Back to top page