Zobrist Hash (立方数判定) (Hash/zobrist_cubic_hash.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2024-10-01 17:50:29+09:00
Include: #include "Hash/zobrist_cubic_hash.hpp"

ZobristCubicHash

ZobristCubicHash は、Zobrist Hash を用いて指定範囲の数値列に含まれる 数値の総積を因数ごとに 3 で割った余りに置き換えた値 のハッシュ値を計算するクラスです。
累積ハッシュ値が 0 のとき、指定範囲の値の総積は立方数であると判定できます。

コンストラクタ

ZobristCubicHash(const vector<long long>& v)

数値列 v 全体の累積ハッシュを初期化します。

計算量 v に含まれる要素の最大値をMとしたとき

$O(N \log M)$

get_range_hash

unsigned long long get_range_hash(int l, int r)

指定された範囲 [l, r) の数値列に含まれる要素の累積ハッシュ値を返します。

制約配列vの大きさをNとしたとき

$0 \leq l \lt r \leq N $

計算量

$O(1)$

Depends on

Verified with

test/Hash/zobrist_hash/abc238-g.cpp

Code

#include "Hash/zobrist_hash_base.hpp"
#include "Math/prime_factorize.hpp"

#include <bits/stdc++.h>
using namespace std;

class ZobristCubicHash : private ZobristHashBase
{
private:
    void build(const vector<long long> &v) override
    {
        hash_vector = vector<unsigned long long>(v.size() + 1, 0);

        unordered_map<long long, long long> prime_counts;
        for (int i = 0; i < v.size(); i++)
        {
            hash_vector[i + 1] = hash_vector[i];
            for (auto [p, cnt] : prime_factorize(v[i]))
            {
                cnt %= 3;
                for (int j = 0; j < cnt; j++)
                {
                    prime_counts[p]++;
                    if (prime_counts[p] % 3 == 0)
                    {
                        hash_vector[i + 1] ^= ZobristHashBase::hash(p);
                    }
                    if (prime_counts[p] % 3 == 1)
                    {
                        hash_vector[i + 1] ^= ZobristHashBase::hash(p * p);
                    }
                    if (prime_counts[p] % 3 == 2)
                    {
                        hash_vector[i + 1] ^= ZobristHashBase::hash(p) ^ ZobristHashBase::hash(p * p);
                    }
                }
            }
        }
    }

public:
    unsigned long long get_range_hash(int l, int r) const override
    {
        assert(0 <= l && l < r && r < hash_vector.size());
        return hash_vector[r] ^ hash_vector[l];
    }

    ZobristCubicHash(const vector<long long> &v)
    {
        build(v);
    };
};

#line 1 "Hash/zobrist_hash_base.hpp"
#include <bits/stdc++.h>
using namespace std;

class ZobristHashBase
{
private:
    static unsigned long long splitmix64(uint64_t x)
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    static unsigned long long generate_random_value(unsigned long long x)
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }

protected:
    static unsigned long long hash(long long x)
    {
        static unordered_map<long long, unsigned long long> cache;
        if (cache.contains(x))
        {
            return cache[x];
        }

        cache[x] = generate_random_value(x);
        return cache[x];
    };

    virtual void build(const vector<long long> &v) = 0;
    ZobristHashBase() {};

public:
    vector<unsigned long long> hash_vector;
    virtual unsigned long long get_range_hash(int l, int r) const = 0;
    virtual ~ZobristHashBase() = default;
};
#line 2 "Math/prime_factorize.hpp"
using namespace std;

vector<pair<long long, long long>> prime_factorize(long long N)
{
    assert(0 < N);

    long long tempN = N;
    vector<pair<long long, long long>> dst;
    for (long long i = 2; i * i <= tempN; i++)
    {
        if (N % i == 0)
        {
            dst.push_back(make_pair(i, 0));
            while (N % i == 0)
            {
                dst.back().second++;
                N /= i;
            }
        }
    }
    if (N != 1)
        dst.push_back(make_pair(N, 1));
    return dst;
}
#line 3 "Hash/zobrist_cubic_hash.hpp"

#line 5 "Hash/zobrist_cubic_hash.hpp"
using namespace std;

class ZobristCubicHash : private ZobristHashBase
{
private:
    void build(const vector<long long> &v) override
    {
        hash_vector = vector<unsigned long long>(v.size() + 1, 0);

        unordered_map<long long, long long> prime_counts;
        for (int i = 0; i < v.size(); i++)
        {
            hash_vector[i + 1] = hash_vector[i];
            for (auto [p, cnt] : prime_factorize(v[i]))
            {
                cnt %= 3;
                for (int j = 0; j < cnt; j++)
                {
                    prime_counts[p]++;
                    if (prime_counts[p] % 3 == 0)
                    {
                        hash_vector[i + 1] ^= ZobristHashBase::hash(p);
                    }
                    if (prime_counts[p] % 3 == 1)
                    {
                        hash_vector[i + 1] ^= ZobristHashBase::hash(p * p);
                    }
                    if (prime_counts[p] % 3 == 2)
                    {
                        hash_vector[i + 1] ^= ZobristHashBase::hash(p) ^ ZobristHashBase::hash(p * p);
                    }
                }
            }
        }
    }

public:
    unsigned long long get_range_hash(int l, int r) const override
    {
        assert(0 <= l && l < r && r < hash_vector.size());
        return hash_vector[r] ^ hash_vector[l];
    }

    ZobristCubicHash(const vector<long long> &v)
    {
        build(v);
    };
};