渡された vector の各要素に対して、ハッシュ値を割り当てる
(Others/ZobristHash.hpp)

• View this file on GitHub
• Last update: 2025-05-11 23:56:10+09:00
• Include: #include "Others/ZobristHash.hpp"

Depends on

• Others/macros.hpp

Code

#ifndef ZobristHash_HPP
#define ZobristHash_HPP

#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <limits>
#include <algorithm>
#include <random>

#include "macros.hpp"

template <typename T>
struct ZobristHash {
private:
    std::map<T, int> hash_;

public:
    /**
     * @brief 渡された vector の各要素に対して、ハッシュ値を割り当てる
     * @remark 複数の vector を同時に渡すことができる
     */
    template <typename... Args>
    ZobristHash(const Args&... vecs) {
        std::vector<T> merged;
        (merged.insert(merged.end(), vecs.begin(), vecs.end()), ...);

        std::sort(merged.begin(), merged.end());
        merged.erase(std::unique(merged.begin(), merged.end()), merged.end());

        std::random_device rd;
        std::mt19937 mt(rd());
        std::uniform_int_distribution<int> ran(0, std::numeric_limits<int>::max()); // int 型の範囲で割り当てる（ただし、非負整数）

        for (const auto& e : merged) {
            hash_[e] = ran(mt);
        }
    }

    /**
     * @brief 引数に割り当てられたハッシュ値を返す
     */
    int val(const T& e) {
        assert(hash_.find(e) != hash_.end());
        return hash_[e];
    }

    /**
     * @brief 各要素のハッシュ値の XOR を取る ver
     * @remark set として（multiset ではない！）の一致判定を O(1) で行うことができる
     * @return 引数で渡された vector<T> vec の、各要素のハッシュ値の累積 XOR を取ったもの
     */
    std::vector<ll> hash_pref_xor(const std::vector<T>& vec) {
        int N = vec.size();
        std::vector<ll> pref(N + 1);
        std::unordered_set<T> memo;

        for (int i = 0; i < N; i++) {
            if (memo.find(vec[i]) == memo.end()) {
                memo.insert(vec[i]);
                pref[i + 1] = pref[i] ^ val(vec[i]);
            } else {
                pref[i + 1] = pref[i];
            }
        }

        return pref;
    }

    /**
     * @brief 各要素のハッシュ値の累積和をとる ver
     * @remark multiset としての一致判定を O(1) で行うことができる
     * @return 引数で渡された vector<T> vec の、各要素のハッシュ値の累積和を取ったもの
     */
    std::vector<ll> hash_pref_sum(const std::vector<T>& vec) {
        int N = vec.size();
        std::vector<ll> pref(N + 1);

        for (int i = 0; i < N; i++) {
            pref[i + 1] = pref[i] + val(vec[i]);
        }

        return pref;
    }
};

#endif // ZobristHash_HPP

#line 1 "Others/ZobristHash.hpp"



#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <limits>
#include <algorithm>
#include <random>

#line 1 "Others/macros.hpp"



#line 5 "Others/macros.hpp"
#include <queue>
#include <cmath>

using ll = long long;
using lll = __int128_t;
using ld = long double;
#define newl '\n'
#define REF const auto&
#define INF 1000390039
#define LLINF 1000000039000000039
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LLMAX LONG_LONG_MAX
#define LLMIN LONG_LONG_MIN
#define BIT(i) (1LL << (i))
#define tbit(n, k) ((n >> k) & 1) // nの（上から）kビット目
#define bit(n, k) (n & (1LL << (k))) // nの（下から）kビット目
#define PI acos(-1)
#define inr(l, x, r) (l <= x && x < r)
#define einr(l, x, r) (l <= x && x <= r)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define erep(i, a, b) for(int i = (a); i <= (b); i++)
#define rrep(i, a, b) for(int i = (a); i >= (b); i--)
#define repl(i, a, b) for(long long i = (a); i < (b); i++)
#define erepl(i, a, b) for(long long i = (a); i <= (b); i++)
#define rrepl(i, a, b) for(long long i = (a); i >= (b); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define FOR_subset(sub, bit) for (ll sub = (bit); sub >= 0; sub = (sub == 0 ? -1 : (sub - 1) & (bit)))
#define UNIQUE(v) (std::sort(all(v)), (v).erase(std::unique(all(v)), (v).end()))
#define pcnt(x) __builtin_popcount(x)
#define llpcnt(x) __builtin_popcountll(x)
#define VC(name, type, ...) vector<type> name(__VA_ARGS__)
#define VVC(name, type, a, ...) vector<vector<type>> name(a, vector<type>(__VA_ARGS__))
#define VVVC(name, type, a, b, ...) vector<vector<vector<type>>> name(a, vector<vector<type>>(b, vector<type>(__VA_ARGS__)))
#define VVVVC(name, type, a, b, c, ...) vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
#define VVVVVC(name, type, a, b, c, d, ...) vector<vector<vector<vector<vector<type>>>>> name(a, vector<vector<vector<vector<type>>>>(b, vector<vector<vector<type>>>(c, vector<vector<type>>(d, vector<type>(__VA_ARGS__)))));
template <typename T>
int lwb(const std::vector<T>& vec, const T& x){
    return lower_bound(all(vec), x) - vec.begin();
}
template <typename T>
int upb(const std::vector<T>& vec, const T& x){
    return upper_bound(all(vec), x) - vec.begin();
}
template <typename T>
T max(const std::vector<T>& vec){ return *max_element(all(vec)); }
template <typename T>
T min(const std::vector<T>& vec){ return *min_element(all(vec)); }
template <typename T>
T rad(const T& x){ return x * PI/180; }
template <typename T>
using maxpq = std::priority_queue<T>;
template <typename T>
using minpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
// 最大値・最小値の更新
template <typename T1, typename T2>
bool chmax(T1 &a, const T2& b){
    if (a < b) { a = b; return 1; }
    return 0;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2& b){
    if (a > b) { a = b; return 1; }
    return 0;
}

const int di4[4] = {-1, 0, 1, 0};
const int dj4[4] = {0, 1, 0, -1};
const int di8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dj8[8] = {0, 1, 1, 1, 0, -1, -1, -1};

bool out_of_grid(const int& i, const int& j, const int& h, const int& w){
    if(i < 0 || j < 0 || i >= h || j >= w) return true;
    return false;
}


#line 13 "Others/ZobristHash.hpp"

template <typename T>
struct ZobristHash {
private:
    std::map<T, int> hash_;

public:
    /**
     * @brief 渡された vector の各要素に対して、ハッシュ値を割り当てる
     * @remark 複数の vector を同時に渡すことができる
     */
    template <typename... Args>
    ZobristHash(const Args&... vecs) {
        std::vector<T> merged;
        (merged.insert(merged.end(), vecs.begin(), vecs.end()), ...);

        std::sort(merged.begin(), merged.end());
        merged.erase(std::unique(merged.begin(), merged.end()), merged.end());

        std::random_device rd;
        std::mt19937 mt(rd());
        std::uniform_int_distribution<int> ran(0, std::numeric_limits<int>::max()); // int 型の範囲で割り当てる（ただし、非負整数）

        for (const auto& e : merged) {
            hash_[e] = ran(mt);
        }
    }

    /**
     * @brief 引数に割り当てられたハッシュ値を返す
     */
    int val(const T& e) {
        assert(hash_.find(e) != hash_.end());
        return hash_[e];
    }

    /**
     * @brief 各要素のハッシュ値の XOR を取る ver
     * @remark set として（multiset ではない！）の一致判定を O(1) で行うことができる
     * @return 引数で渡された vector<T> vec の、各要素のハッシュ値の累積 XOR を取ったもの
     */
    std::vector<ll> hash_pref_xor(const std::vector<T>& vec) {
        int N = vec.size();
        std::vector<ll> pref(N + 1);
        std::unordered_set<T> memo;

        for (int i = 0; i < N; i++) {
            if (memo.find(vec[i]) == memo.end()) {
                memo.insert(vec[i]);
                pref[i + 1] = pref[i] ^ val(vec[i]);
            } else {
                pref[i + 1] = pref[i];
            }
        }

        return pref;
    }

    /**
     * @brief 各要素のハッシュ値の累積和をとる ver
     * @remark multiset としての一致判定を O(1) で行うことができる
     * @return 引数で渡された vector<T> vec の、各要素のハッシュ値の累積和を取ったもの
     */
    std::vector<ll> hash_pref_sum(const std::vector<T>& vec) {
        int N = vec.size();
        std::vector<ll> pref(N + 1);

        for (int i = 0; i < N; i++) {
            pref[i + 1] = pref[i] + val(vec[i]);
        }

        return pref;
    }
};

Back to top page