ロリハをセグ木にのせる時のモノイド
(Src/Algebra/Monoid/RollingHashMonoid.hpp)

• View this file on GitHub
• Last update: 2024-12-06 16:40:42+09:00
• Include: #include "Src/Algebra/Monoid/RollingHashMonoid.hpp"

概要

RollingHashMonoidData: セグ木に乗っているデータ

• staticメンバ関数randomValue(Value sigma) でsigma+1 ~ MOD - 1のランダムな値を生成します
• staticメンバ変数baseを必ず初期化してください (RollingHashMonoidData::randomValueを使うのが一番無難な選択です)
• operator== operator!=が定義されています

RollingHashMonoid: 結合とかの関数が定義されている。

Depends on

• Src/Number/Mersenne61ModInt.hpp
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• Test/AOJ/0478.test.cpp
• AOJ3548 String Puzzle (Test/AOJ/3548.test.cpp)
• Test/AtCoder/abc331_f.test.cpp

Code

#pragma once

#include "../../Template/TypeAlias.hpp"
#include "../../Number/Mersenne61ModInt.hpp"

#include <random>
#include <type_traits>

namespace zawa {

struct RollingHashMonoidData {
    using Value = Mersenne61ModInt::Value;
    using Size = usize;
    static Value base;
    Value hash{}, pow{1};
    usize len{};

    constexpr RollingHashMonoidData() = default;
    constexpr RollingHashMonoidData(Value h, Value p, usize l) : hash{h}, pow{p}, len{l} {}
    template <class T>
    constexpr RollingHashMonoidData(const T& v) 
        : hash{static_cast<Value>(v)}, pow{base}, len{1} {}
    // RollingHashMonoidData(const RollingHashMonoidData& data)
    //     : hash{data.hash}, pow{data.pow}, len{data.len} {}
    
    static Value randomValue(const Value& sigma) {
        return std::mt19937{std::random_device{}()}() % (Mersenne61ModInt::Mod() - sigma) + sigma + 1;
    }

    friend constexpr bool operator==(const RollingHashMonoidData& lhs, const RollingHashMonoidData& rhs) {
        return lhs.hash == rhs.hash and lhs.len == rhs.len;
    }
    friend constexpr bool operator!=(const RollingHashMonoidData& lhs, const RollingHashMonoidData& rhs) {
        return lhs.hash != rhs.hash or lhs.len != rhs.len;
    }
};

struct RollingHashMonoid {
    using Modulo = Mersenne61ModInt;
    using Element = RollingHashMonoidData;
    static constexpr Element identity() noexcept {
        return Element{};
    }
    static constexpr Element operation(const Element& lhs, const Element& rhs) noexcept {
        return Element{
            Modulo::Modulo(Modulo::UnsafeMul(lhs.hash, rhs.pow) + rhs.hash),
            Modulo::Mul(lhs.pow, rhs.pow),
            lhs.len + rhs.len
        };
    }
};

} // namespace zawa

#line 2 "Src/Algebra/Monoid/RollingHashMonoid.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 2 "Src/Number/Mersenne61ModInt.hpp"

#line 4 "Src/Number/Mersenne61ModInt.hpp"

namespace zawa {

// @reference: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
class Mersenne61ModInt {
public:
    using Value = u64;
private:
    static constexpr Value MOD{(1ull << 61) - 1}; // == MASK61
    static constexpr Value MASK30{(1ull << 30) - 1};
    static constexpr Value MASK31{(1ull << 31) - 1};
    Value v_{};
public:
    constexpr Mersenne61ModInt() {}

    static constexpr Value Mod() noexcept {
        return MOD;
    }
    static constexpr Value Modulo(const Value& v) noexcept {
        Value res{(v >> 61) + (v & MOD)};
        res = (res >= MOD ? res - MOD : res);
        return res;
    }
    static constexpr Value UnsafeMul(const Value& a, const Value& b) noexcept {
        Value fa{a >> 31}, fb{b >> 31};
        Value ba{a & MASK31}, bb{b & MASK31};
        Value mid{fa * bb + fb * ba};
        return Value{2}*fa*fb + (mid >> 30) + ((mid & MASK30) << 31) + ba*bb;
    }
    static constexpr Value Mul(const Value& a, const Value& b) noexcept {
        return Modulo(UnsafeMul(a, b));
    }
};

};
#line 5 "Src/Algebra/Monoid/RollingHashMonoid.hpp"

#include <random>
#include <type_traits>

namespace zawa {

struct RollingHashMonoidData {
    using Value = Mersenne61ModInt::Value;
    using Size = usize;
    static Value base;
    Value hash{}, pow{1};
    usize len{};

    constexpr RollingHashMonoidData() = default;
    constexpr RollingHashMonoidData(Value h, Value p, usize l) : hash{h}, pow{p}, len{l} {}
    template <class T>
    constexpr RollingHashMonoidData(const T& v) 
        : hash{static_cast<Value>(v)}, pow{base}, len{1} {}
    // RollingHashMonoidData(const RollingHashMonoidData& data)
    //     : hash{data.hash}, pow{data.pow}, len{data.len} {}
    
    static Value randomValue(const Value& sigma) {
        return std::mt19937{std::random_device{}()}() % (Mersenne61ModInt::Mod() - sigma) + sigma + 1;
    }

    friend constexpr bool operator==(const RollingHashMonoidData& lhs, const RollingHashMonoidData& rhs) {
        return lhs.hash == rhs.hash and lhs.len == rhs.len;
    }
    friend constexpr bool operator!=(const RollingHashMonoidData& lhs, const RollingHashMonoidData& rhs) {
        return lhs.hash != rhs.hash or lhs.len != rhs.len;
    }
};

struct RollingHashMonoid {
    using Modulo = Mersenne61ModInt;
    using Element = RollingHashMonoidData;
    static constexpr Element identity() noexcept {
        return Element{};
    }
    static constexpr Element operation(const Element& lhs, const Element& rhs) noexcept {
        return Element{
            Modulo::Modulo(Modulo::UnsafeMul(lhs.hash, rhs.pow) + rhs.hash),
            Modulo::Mul(lhs.pow, rhs.pow),
            lhs.len + rhs.len
        };
    }
};

} // namespace zawa

Back to top page