随机数mt19937

当时写题想生成大范围的随机数，rand() 那点随机性根本不够看。后来换成了 mt19937 这套模板，顺手把每一行到底在干嘛也搞清楚了。这篇就按我的理解拆一遍。

---

1. <chrono>：时间库

#include <chrono>

• C++11 引入的时间处理头文件，提供各种时钟和时间点、时长的类型。
• 这里我们用到了 std::chrono::steady_clock，它表示一个“稳步”时钟（monotonic clock），不会被系统时间调整影响，非常适合用来做计时或生成随机数种子。

---

2. 获取时间戳：steady_clock::now().time_since_epoch().count()

std::chrono::steady_clock::now()

• 取得当前时刻的一个时间点（time_point）。

.time_since_epoch()

• 这个时间点距离“纪元”（epoch，即时钟的起点，通常是程序启动后或者系统某个固定时刻）过去了多长时间，类型是 duration（时长）。

.count()

• 把时长转换为其底层整数表示，比如纳秒或毫秒数，得到一个整数值。例如，如果底层精度是纳秒，就会返回从 epoch 开始到现在的纳秒数。

总结：合起来看，就是拿当前“稳步时钟”的时间当作一个大整数，丢给随机数引擎当种子（seed）。

---

3. <random>：随机数库

#include <random>

• C++11 提供的真正“现代化”的随机数生成库，包含多种随机数引擎和多种分布。

---

4. 伪随机数引擎：std::mt19937_64 rng(seed);

std::mt19937_64 rng( /* seed */ );

• mt19937_64：一种基于 Mersenne Twister 算法的 64 位伪随机数引擎。

  • 周期超长（2²⁰⁰⁰³⁷−1），统计学性质良好，速度也很快。
  • _64 表示输出是 64 位整数。

• 构造时传一个 unsigned long long 类型的种子，我习惯用时间戳，保证每次运行生成的序列都不一样。

---

5. 随机分布：std::uniform_int_distribution<int>

std::uniform_int_distribution<int> dist(l, r);

• 作用：把伪随机数引擎产生的原始随机位流（通常是非常大的 64 位整数）映射成 闭区间 [l, r] 上的 均匀分布 整数。
• 每次调用 dist(rng) 时，底层会自动从 [l, r] 范围内取一个均匀分布的整数。

---

6. 宏定义：randInt(l, r)

#define randInt(l, r) ( std::uniform_int_distribution<int>((l),(r))(rng) )

• 这是一个宏，调用时写 randInt(10, 20)，预处理后就变成：

( std::uniform_int_distribution<int>(10,20)(rng) )

• 等价于：

std::uniform_int_distribution<int> __d(10,20);
int x = __d(rng);

• 每次执行都会在 [l, r] 范围内取一个新的随机整数。

---

7. 使用示例

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

// 1) 以当前时间戳初始化 64 位 Mersenne Twister 引擎
static mt19937_64 rng(
    chrono::steady_clock::now().time_since_epoch().count()
);

// 2) 宏：在 [l, r] 范围内生成均匀随机整数
#define randInt(l, r) ( uniform_int_distribution<int>((l),(r))(rng) )

int main() {
    FAST_IO();  // 如果你定义了 FAST_IO 宏，可以加上

    // 生成 5 个 [1,100] 之间的随机数
    for (int i = 0; i < 5; i++) {
        int x = randInt(1, 100);
        cout << x << ' ';
    }
    cout << '\n';

    // 随机打乱一个数组
    vector<int> a = {1,2,3,4,5};
    shuffle(a.begin(), a.end(), rng);
    for (int v : a) cout << v << ' ';
    cout << '\n';

    return 0;
}

运行结果示例：

42 7 89 13 55
3 5 1 4 2

---

8. 为什么要这样做？

1. 比 rand() 更好

   • rand() 只有 15 位或更少的随机性（RAND_MAX 通常是 2¹⁵−1），容易周期短、分布不均。
   • mt19937_64 能提供 64 位以上的状态空间，分布质量和周期都更好。

2. 用时间戳作种子

   • 每次程序启动时，steady_clock::now() 都不一样，保证随机序列不重复。
   • 如果想复现同一序列，可以把种子写死，例如 mt19937_64 rng(20250618);。

3. 统一管理

   • 只需一个全局 rng，所有分布都用这一个引擎。
   • 方便在不同分布（均匀、正态、泊松……）之间切换。

---

小贴士

• 如果你需要生成更大范围的随机整数（比如 long long），可以用：

#define randLL(l, r) ( uniform_int_distribution<long long>((l),(r))(rng) )

• 如果想要浮点随机数：

uniform_real_distribution<double> dist(0.0, 1.0);
double y = dist(rng);  // 在 [0,1] 上的均匀实数

• 注意：别在循环里反复 re-seed（比如每轮都用时间戳重新初始化 rng），多次快速调用时时间戳可能相同，反而生成一堆重复的“随机”数。

---

所以最后真正要记住的，其实就是下面这两行：

static mt19937_64 rng(
    chrono::steady_clock::now().time_since_epoch().count()
);
#define randInt(l, r) ( uniform_int_distribution<int>((l),(r))(rng) )

我自己就是靠这套在赛场上“造随机”的，希望它也能帮到你。