random/random_generator.hpp

• View this file on GitHub
• Last update: 2025-02-10 07:44:08+09:00
• Include: #include "random/random_generator.hpp"

Code

namespace RNG {
static mt19937_64 engine(clock());
template <typename T = long long> T rnd(T l, T r) {
    return engine() % (r - l) + l;
}
string rndstr(ll len, char l, char r) {
    string res;
    for (int i = 0; i < len; i++) res += l + rnd(0, int(r - l));
    return res;
}
template <typename T> vector<T> rndvec(ll len, T l, T r) {
    vector<T> res(len);
    for (T &x : res) x = rnd<T>(l, r);
    return res;
}
vector<pair<int, int>> rndtree(int n) {
    vector<pair<int, int>> res;
    atcoder::dsu uf(n);
    while (uf.size(0) != n) {
        int u = rnd(0, n);
        int v = rnd(0, n - 1);
        if (v >= u) v++;
        if (uf.same(u, v))
            continue;
        else {
            uf.merge(u, v);
            res.emplace_back(u, v);
        }
    }
    return res;
}

template <bool simple> vector<pair<int, int>> rndgraph(int n, int m) {
    vector<pair<int, int>> res;
    set<pair<int, int>> cnt;
    while (int(res.size()) < m) {
        int u = rnd(0, n);
        int v = rnd(0, n);
        if (u == v && simple) continue;
        if (u > v) swap(u, v);
        if (simple && cnt.count(make_pair(u, v))) continue;
        res.emplace_back(u, v);
        if (simple) cnt.insert(make_pair(u, v));
    }
    return res;
}  // 連結とは限らないから注意

template <bool simple> vector<pair<int, int>> rndgraph_connected(int n) {
    vector<pair<int, int>> res;
    set<pair<int, int>> cnt;
    atcoder::dsu uf(n);
    while (uf.size(0) != n) {
        int u = rnd(0, n);
        int v = rnd(0, n);
        if (u == v && simple) continue;
        if (u > v) swap(u, v);
        if (simple && cnt.count(make_pair(u, v))) continue;
        res.emplace_back(u, v);
        uf.merge(u, v);
        if (simple) cnt.insert(make_pair(u, v));
    }
    return res;
}

template <typename T> vector<vector<T>> vector_all(int n, T l, T r) {
    vector<vector<T>> ret;
    auto dfs = [&](auto f, int i, vector<T> &v) {
        if (i == n) {
            ret.push_back(v);
            return;
        }
        for (T c = l; c < r; ++c) {
            v.push_back(c);
            f(f, i + 1, v);
            v.pop_back();
        }
    };
    vector<T> t;
    dfs(dfs, 0, t);
    return ret;
}
}  // namespace RNG
using namespace RNG;

#line 1 "random/random_generator.hpp"
namespace RNG {
static mt19937_64 engine(clock());
template <typename T = long long> T rnd(T l, T r) {
    return engine() % (r - l) + l;
}
string rndstr(ll len, char l, char r) {
    string res;
    for (int i = 0; i < len; i++) res += l + rnd(0, int(r - l));
    return res;
}
template <typename T> vector<T> rndvec(ll len, T l, T r) {
    vector<T> res(len);
    for (T &x : res) x = rnd<T>(l, r);
    return res;
}
vector<pair<int, int>> rndtree(int n) {
    vector<pair<int, int>> res;
    atcoder::dsu uf(n);
    while (uf.size(0) != n) {
        int u = rnd(0, n);
        int v = rnd(0, n - 1);
        if (v >= u) v++;
        if (uf.same(u, v))
            continue;
        else {
            uf.merge(u, v);
            res.emplace_back(u, v);
        }
    }
    return res;
}

template <bool simple> vector<pair<int, int>> rndgraph(int n, int m) {
    vector<pair<int, int>> res;
    set<pair<int, int>> cnt;
    while (int(res.size()) < m) {
        int u = rnd(0, n);
        int v = rnd(0, n);
        if (u == v && simple) continue;
        if (u > v) swap(u, v);
        if (simple && cnt.count(make_pair(u, v))) continue;
        res.emplace_back(u, v);
        if (simple) cnt.insert(make_pair(u, v));
    }
    return res;
}  // 連結とは限らないから注意

template <bool simple> vector<pair<int, int>> rndgraph_connected(int n) {
    vector<pair<int, int>> res;
    set<pair<int, int>> cnt;
    atcoder::dsu uf(n);
    while (uf.size(0) != n) {
        int u = rnd(0, n);
        int v = rnd(0, n);
        if (u == v && simple) continue;
        if (u > v) swap(u, v);
        if (simple && cnt.count(make_pair(u, v))) continue;
        res.emplace_back(u, v);
        uf.merge(u, v);
        if (simple) cnt.insert(make_pair(u, v));
    }
    return res;
}

template <typename T> vector<vector<T>> vector_all(int n, T l, T r) {
    vector<vector<T>> ret;
    auto dfs = [&](auto f, int i, vector<T> &v) {
        if (i == n) {
            ret.push_back(v);
            return;
        }
        for (T c = l; c < r; ++c) {
            v.push_back(c);
            f(f, i + 1, v);
            v.pop_back();
        }
    };
    vector<T> t;
    dfs(dfs, 0, t);
    return ret;
}
}  // namespace RNG
using namespace RNG;

Back to top page