random/gen.hpp

• View this file on GitHub
• Last update: 2025-04-05 12:46:42+09:00
• Include: #include "random/gen.hpp"

Depends on

• random/seed.hpp

Required by

• fps/poly_find_root.hpp
• math/group/rolling_hash.hpp
• math/group/rolling_hash.hpp
• math/group/rolling_hash.hpp
• math/multiplicative_function/euler_phi.hpp
• math/multiplicative_function/mobius.hpp
• math/multiplicative_function/sigma.hpp
• math/prime_factorize.hpp
• math_mod/primitive_root_64bit.hpp
• math_mod/primitive_root_64bit.hpp
• random/graph.hpp
• random/hash.hpp
• random/hash.hpp
• random/hash.hpp
• 文字の一点更新が可能文字列に対する動的なローリングハッシュ (string/dynamic_rolling_hash.hpp)
• 文字の一点更新が可能文字列に対する動的なローリングハッシュ (string/dynamic_rolling_hash.hpp)
• 文字の一点更新が可能文字列に対する動的なローリングハッシュ (string/dynamic_rolling_hash.hpp)
• 文字の変更が行われない文字列に対する静的なローリングハッシュ (string/static_rolling_hash.hpp)
• 文字の変更が行われない文字列に対する静的なローリングハッシュ (string/static_rolling_hash.hpp)
• 文字の変更が行われない文字列に対する静的なローリングハッシュ (string/static_rolling_hash.hpp)

Verified with

• verify/aoj/aoj_alds1_14_b.test.cpp
• verify/aoj/aoj_alds1_14_b.test.cpp
• verify/aoj/aoj_alds1_14_b.test.cpp
• verify/aoj/aoj_ntl_1_d.test.cpp
• verify/unit_test/action.test.cpp
• verify/unit_test/binom_table.test.cpp
• verify/unit_test/bit_vector.test.cpp
• verify/unit_test/famous_function_table.test.cpp
• verify/unit_test/famous_function_table.test.cpp
• verify/unit_test/isprime_table_extend.test.cpp
• verify/unit_test/large_fact_arb_mod.test.cpp
• verify/unit_test/lpf_table_extend.test.cpp
• verify/unit_test/lpf_table_extend.test.cpp
• verify/unit_test/monoid.test.cpp
• verify/unit_test/monoid.test.cpp
• verify/unit_test/monoid.test.cpp
• verify/unit_test/monoid.test.cpp
• verify/unit_test/multiplicative_function_table.test.cpp
• verify/unit_test/offline_dynamic_connectivity.test.cpp
• verify/unit_test/partial_persitent_unionfind.test.cpp
• verify/unit_test/prime_factorize_table.test.cpp
• verify/unit_test/prime_factorize_table.test.cpp
• verify/unit_test/prime_table_extend.test.cpp
• verify/unit_test/wavelet_matrix.test.cpp
• verify/yosupo_fps/poly_root_finding.test.cpp
• verify/yosupo_math/factrize.test.cpp
• verify/yosupo_math/primitive_root.test.cpp
• verify/yosupo_math/primitive_root.test.cpp
• verify/yosupo_string/string_z_roliha.test.cpp
• verify/yosupo_string/string_z_roliha.test.cpp
• verify/yosupo_string/string_z_roliha.test.cpp

Code

#ifndef KK2_RANDOM_GEN_HPP
#define KK2_RANDOM_GEN_HPP 1

#include <algorithm>
#include <cassert>
#include <numeric>
#include <random>
#include <unordered_set>
#include <vector>

#include "seed.hpp"

namespace kk2 {

namespace random {

using i64 = long long;
using u64 = unsigned long long;

inline u64 rng() {
    static std::mt19937_64 mt(kk2::random::seed());
    return mt();
}

// [l, r)
inline i64 rng(i64 l, i64 r) {
    assert(l < r);
    return l + rng() % (r - l);
}

// [l, r)
template <class T> std::vector<T> random_vector(int n, T l, T r) {
    std::vector<T> res(n);
    for (int i = 0; i < n; i++) res[i] = rng(l, r);
    return res;
}

// [l, r)
std::vector<i64> distinct_rng(i64 l, i64 r, i64 n) {
    assert(l < r and n <= r - l);
    std::unordered_set<i64> st;
    for (i64 i = n; i; --i) {
        i64 m = rng(l, r + 1 - i);
        if (st.find(m) != st.end()) m = r - i;
        st.insert(m);
    }
    std::vector<i64> res(st.begin(), st.end());
    std::sort(res.begin(), res.end());
    return res;
}

template <class Iter> void shuffle(Iter first, Iter last) {
    if (first == last) return;
    int len = 1;
    for (auto it = first + 1; it != last; ++it) {
        len++;
        int j = rng(0, len);
        if (j != len - 1) std::iter_swap(first + j, it);
    }
}

template <class T> std::vector<T> perm(int n) {
    std::vector<T> res(n);
    std::iota(res.begin(), res.end(), T(0));
    shuffle(res.begin(), res.end());
    return res;
}

template <class T> std::vector<T> choices(int l, int r, int k) {
    assert(l < r and k <= r - l);
    std::vector<T> res(r - l);
    std::iota(res.begin(), res.end(), T(l));
    shuffle(res.begin(), res.end());
    res.resize(k);
    return res;
}

} // namespace random

} // namespace kk2

#endif // KK2_RANDOM_GEN_HPP

#line 1 "random/gen.hpp"



#include <algorithm>
#include <cassert>
#include <numeric>
#include <random>
#include <unordered_set>
#include <vector>

#line 1 "random/seed.hpp"



#include <chrono>

namespace kk2 {

namespace random {

using u64 = unsigned long long;

inline u64 non_deterministic_seed() {
    u64 seed = std::chrono::duration_cast<std::chrono::nanoseconds>(
                   std::chrono::high_resolution_clock::now().time_since_epoch())
                   .count();
    seed ^= reinterpret_cast<u64>(&seed);
    seed ^= seed << 5;
    seed ^= seed >> 41;
    seed ^= seed << 20;
    return seed;
}

inline u64 deterministic_seed() { return 5801799128519729247ull; }

inline u64 seed() {
#if defined(KK2_RANDOM_DETERMINISTIC)
    return deterministic_seed();
#else
    return non_deterministic_seed();
#endif
}

} // namespace random

} // namespace kk2


#line 12 "random/gen.hpp"

namespace kk2 {

namespace random {

using i64 = long long;
using u64 = unsigned long long;

inline u64 rng() {
    static std::mt19937_64 mt(kk2::random::seed());
    return mt();
}

// [l, r)
inline i64 rng(i64 l, i64 r) {
    assert(l < r);
    return l + rng() % (r - l);
}

// [l, r)
template <class T> std::vector<T> random_vector(int n, T l, T r) {
    std::vector<T> res(n);
    for (int i = 0; i < n; i++) res[i] = rng(l, r);
    return res;
}

// [l, r)
std::vector<i64> distinct_rng(i64 l, i64 r, i64 n) {
    assert(l < r and n <= r - l);
    std::unordered_set<i64> st;
    for (i64 i = n; i; --i) {
        i64 m = rng(l, r + 1 - i);
        if (st.find(m) != st.end()) m = r - i;
        st.insert(m);
    }
    std::vector<i64> res(st.begin(), st.end());
    std::sort(res.begin(), res.end());
    return res;
}

template <class Iter> void shuffle(Iter first, Iter last) {
    if (first == last) return;
    int len = 1;
    for (auto it = first + 1; it != last; ++it) {
        len++;
        int j = rng(0, len);
        if (j != len - 1) std::iter_swap(first + j, it);
    }
}

template <class T> std::vector<T> perm(int n) {
    std::vector<T> res(n);
    std::iota(res.begin(), res.end(), T(0));
    shuffle(res.begin(), res.end());
    return res;
}

template <class T> std::vector<T> choices(int l, int r, int k) {
    assert(l < r and k <= r - l);
    std::vector<T> res(r - l);
    std::iota(res.begin(), res.end(), T(l));
    shuffle(res.begin(), res.end());
    res.resize(k);
    return res;
}

} // namespace random

} // namespace kk2

Back to top page