PermutedCongruentialGenerator
(src/random/permuted_congruential_generator.hpp)

• View this file on GitHub
• Last update: 2025-04-27 00:17:33+09:00
• Include: #include "src/random/permuted_congruential_generator.hpp"

PermutedCongruentialGenerator

• 一様ランダムな整数・実数

を生成します．

メルセンヌツイスタを用いた RandomNumberGenerator よりやや質が悪いですが，かなり高速です． アルゴリズムコンテストでは RandomNumberGenerator を使い，ヒューリスティックコンテストでは PermutedCongruentialGenerator を使うことを推奨します．

コンストラクタ

PermutedCongruentialGenerator rng()

• 乱数生成器 rng を作成します．シードには実行時の時刻を用いています．

計算量

• $O(1)$

operator ()

T rng(T l, T r)

$[l, r]$ の範囲の整数・実数を一様ランダムに返します．

制約

• $l \leq r$
• T は int か unsigned int か double

計算量

• $O(1)$

Depends on

• template (src/template/template.hpp)

Verified with

• verify/unit_test/convolution/convolution_ll.test.cpp
• verify/unit_test/convolution/or_convolution.test.cpp

Code

#pragma once
#include "../template/template.hpp"
struct PermutedCongruentialGenerator {
    template <typename T>
        requires(is_integral_v<T> and sizeof(T) == 4) or (is_floating_point_v<T> and sizeof(T) == 8)
    inline T operator()(const T l, const T r) {
        assert(l <= r);
        if constexpr(is_integral_v<T>) {
            const unsigned int range = static_cast<unsigned int>(r - l + 1);
            return l + (next32() % range);
        } else {
            static constexpr unsigned long long denom = 1ull << 53;
            const unsigned long long x = next64() >> 11;
            const double u = static_cast<double>(x) / denom;
            return l + (r - l) * u;
        }
    }

   private:
    static constexpr unsigned long long MULT = 6364136223846793005;
    static inline unsigned long long state = chrono::steady_clock::now().time_since_epoch().count();
    inline unsigned int next32() {
        unsigned long long x = state;
        state *= MULT;
        const unsigned int count = x >> 61;
        x ^= x >> 22;
        return static_cast<unsigned int>(x >> (22 + count));
    }
    inline unsigned long long next64() {
        return (static_cast<unsigned long long>(next32()) << 32) | next32();
    }
} rng;

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/random/permuted_congruential_generator.hpp"
struct PermutedCongruentialGenerator {
    template <typename T>
        requires(is_integral_v<T> and sizeof(T) == 4) or (is_floating_point_v<T> and sizeof(T) == 8)
    inline T operator()(const T l, const T r) {
        assert(l <= r);
        if constexpr(is_integral_v<T>) {
            const unsigned int range = static_cast<unsigned int>(r - l + 1);
            return l + (next32() % range);
        } else {
            static constexpr unsigned long long denom = 1ull << 53;
            const unsigned long long x = next64() >> 11;
            const double u = static_cast<double>(x) / denom;
            return l + (r - l) * u;
        }
    }

   private:
    static constexpr unsigned long long MULT = 6364136223846793005;
    static inline unsigned long long state = chrono::steady_clock::now().time_since_epoch().count();
    inline unsigned int next32() {
        unsigned long long x = state;
        state *= MULT;
        const unsigned int count = x >> 61;
        x ^= x >> 22;
        return static_cast<unsigned int>(x >> (22 + count));
    }
    inline unsigned long long next64() {
        return (static_cast<unsigned long long>(next32()) << 32) | next32();
    }
} rng;

Back to top page