为美好的骗分送上祝福——寻觅那些 C++ 打包附赠的随机数生成器

· · 算法·理论

算上本行后本文共 11483 个字符。

第一次投文章广场。管理员大大求过qwq。

本篇文章面向 C/C++ 选手，使用其它语言的同学可以自行出门左转。

逛文章广场的时候发现了这样一篇文章，感觉很有意思，但是发现貌似整个谷都主要聚焦于随机数的应用而对于不同随机数算法的对比分析基本没有涉及，遂写此文。

值得注意的是，本文将不会重点聚焦随机数算法的实现细节（如算法过程、原理等），而会聚焦于分析其在 OI 中的实用性（如生成速度等）、介绍其它较不为人知的随机数算法（最典型的就是后文将要介绍的 __gnu_cxx::simd_fast_mersenne_twister_engine 系列）以及介绍与随机数常常绑定的时间戳函数。

如没有特殊说明，下文所指的随机数均指代伪随机数，这里不再给出随机数、伪随机数等的定义，如有需要可自行搜索查找。

随机数生成器

rand() 函数

rand 函数定义于 <cstdlib> 头文件中，是 C 标准库的一部分。函数原型如下：

int rand(void);

由于 rand 函数在 <random> 加入 C++11 标准前便早已是 C 标准的一部分，因此也成为了在 OI 中最为人所知的随机函数，此处不演示如何使用。

然而 C 标准并没有规定 rand 的具体实现，因此在不同的 C 库、平台、编译器下可能会有不一致的表现。在 GCC 中 rand 函数的实现保证其生成随机数分布的均匀性，然而并不保证 rand()%MOD 后随机数分布的均匀性，同时存在随机数周期过短、生成较慢等诸多问题，因此在实际使用中并不推荐使用。

在 Windows 系统下，rand 函数所生成随机数的范围是 [1, 2^{15}-1]，即 RAND_MAX 的值为 2^{15}-1。如果需要生成大于 RAND_MAX 的随机数，应当使用 rand() << 15 | rand() 生成。

在使用前应使用同样定义于 <cstdlib> 的 srand 函数播种，函数原型如下：

void srand(unsigned int _Seed);

如果没有初始化随机数种子，rand 函数会固定地选取 1 作为其种子，使得每次使用 rand 函数所生成的随机数序列与 srand(1) 得到的随机数序列结果完全一致。

常见的随机数种子是当前时间或者硬件随机数，详见下文。

常见错误包括但不限于使用 rand() * rand() 生成大随机数、未初始化随机数种子等。因此，在使用 rand 时应谨慎之再谨慎。

std::mersenne_twister_engine 系列

梅森旋转算法由松本与西村设计。其主要利用的是梅森素数进行随机数列生成，原理可自行搜索，这里由于作者太菜并不作解释。

梅森旋转算法定义于头文件 <random> 中，在 C++11 及后续标准中随各个预定义随机数生成器被加入。在 C++ 标准中定义了梅森旋转器的基类 std::mersenne_twister_engine 与两个预定义的梅森旋转器 std::mt19937 与 std::mt19937_64，均位于 <random> 中。

::::::info[可我用的是 C++98……]{open}

<random> 在 C++11 中被加入，也就是说你无法在 C++98 或更老的标准中使用。

如果你迫切需要使用，你可以使用 <tr1/random> 替代，在其中定义了 std::tr1::mersenne_twister 与 std::tr1::mt19937 以替代 std::mersenne_twister_engine 与 std::mt19937。详见 TR1 规范。

值得注意的是，<tr1/random> 中并无 std::mt19937_64 的替代。

如果遇到这类情况，建议手动开启 C++11 或以上的语言标准进行评测。如果是在评测中出现的问题，可以尝试与教练交涉。

::::::

在 C++ 一众随机数生成器中，梅森旋转显得比较重，生成速度也较慢，但其优势在于其所生成随机数的周期较长，序列重复的几率较低。

一般使用 std::mt19937 与 std::mt19937_64 即可，前者可生成 unsigned int 范围内的随机数，后者可生成 unsigned long long 范围内的随机数。

以 mt19937 为例，可以用如下语法定义一个梅森旋转器：

std::mt19937 rd1;
std::mt19937 rd2(seed);

其中 rd2 将会使用 seed 作为其随机数种子，而 rd1 的种子将会是一个固定值，在 GCC 中该值为 5489u，如有兴趣可以翻看 <bits/random.h>。

下面给出使用例，这个程序能够生成 n 个位于 [l, r] 区间内的数字并输出，其中 n, l, r 均在 unsigned int 范围内，随机数种子为 1145141919u：

#include <random>
#include <iostream>
using namespace std;

unsigned int n, l, r;
mt19937 rd(1145141919u);

int main(void) {
    cin >> n >> l >> r;
    uniform_int_distribution<int> t(l, r);
    while(n--)cout << t(rd) << endl;
    return 0;
}

::::::info[ちょっと！怎么莫名奇妙冒出来个 uniform_int_distribution？]

往后看你就知道了。

这里你可以姑且认为这里和 rand()%mod 一个道理。

::::::

std::linear_congruential_engine 系列

线性同余算法由 Park、Goodman 以及 Miller 发明。其利用的是线性同余方程：

R_{i+1} = (A \times R_i + B) \bmod P

具体原理可自行搜索。

线性同余算法定义于头文件 <random> 中，在 C++11 及后续标准中随各个预定义随机数生成器被加入。在 C++ 标准中定义了线性同余算法的基类 std::linear_congruential_engine 与两个预定义的线性同余算法（亦被称作“最小标准”） std::minstd_rand0 与 std::minstd_rand，均位于 <random> 中。

::::::info[可我用的是 C++98……]{open}

<random> 在 C++11 中被加入，也就是说你无法在 C++98 或更老的标准中使用。

如果你迫切需要使用，你可以使用 <tr1/random> 替代，在其中定义了 std::tr1::linear_congruential、std::tr1::minstd_rand0 与 std::tr1::minstd_rand 以代替 std::linear_congruential_engine、std::minstd_rand0 与 std::minstd_rand。详见 TR1 规范。

如果遇到这类情况，建议手动开启 C++11 或以上的语言标准进行评测。如果是在评测中出现的问题，可以尝试与教练交涉。

::::::

在 C++ 一众随机数生成器中，线性同余具有较快的速度，但随机数周期较上文介绍的梅森旋转要短。

一般使用 std::minstd_rand0 与 std::minstd_rand 即可，两者均可生成 unsigned int 范围内的随机数。其中后者是较新的“最小标准”。

GCC 中默认随机数种子为 1u。

此外，在 GCC 中定义的默认随机数生成器 std::default_random_engine 是 std::minstd_rand0 的别名。

使用方法可参见上文 std::mersenne_twister_engine 系列。

std::subtract_with_carry_engine 系列

并不是很常用也不是很常见的一个系列。

使用的是带进位减法算法（CPPReference 中文版原文如此，GCC 中的注释里写着 Marsaglia-Zaman Algorithm），貌似是时滞斐波那契算法的一种。定义于头文件 <random> 中，在 C++11 及后续标准中随各个预定义随机数生成器被加入。在 C++ 标准中定义了带进位减法算法的基类 std::subtract_with_carry_engine 与四个预定义的带进位减法算法 std::ranlux24_base、std::ranlux48_base、std::ranlux24 与 std::ranlux48，均位于 <random> 中。

::::::info[可我用的是 C++98……]

<random> 在 C++11 中被加入，也就是说你无法在 C++98 或更老的标准中使用。

如果你迫切需要使用（不过你为什么要迫切使用这玩意呢？），你可以使用 <tr1/random>，在其中定义了 std::tr1::subtract_with_carry、std::tr1::subtract_with_carry_01、std::tr1::ranlux_base_01、std::tr1::ranlux64_base_01、std::tr1::ranlux3、std::tr1::ranlux4、std::tr1::ranlux3_01、std::tr1::ranlux4_01，详情可自行搜索查找，可见 TR1 规范。

上述随机数生成器笔者自己一概没用过。

::::::

GCC 中默认随机数种子为 19780503u。

貌似没什么优点，没什么人用，这里不做过多解释。使用例见上。

std::philox_engine 系列

C++26 里新增的新鲜玩意，在我本地的 GCC 9.3.0 中没有找到，翻了翻 CPPReference 后发现貌似包括 GCC 的 libstdc++、Clang 的 libc++ 和 MSVC 都还没有支持。

::::::info[可我用的是……]

打住。

该生成器系列仍未实装，请耐心等待。

::::::

按照标准的说法是一个基于计数器的随机数生成算法，存储和周期都比较优，而且容易被并行化与向量化（SIMD？）。

在 C++ 标准中定义了 Philox 算法的基类 std::subtract_with_carry_engine 与四个预定义的 Philox 算法 std::philox4x32 与 std::philox4x64，均位于 <random> 中。

由于没有实装这里不做过多解释。

std::knuth_b

不是很了解。看 <bits/random.h> 里应该是对于 std::minstd_rand0 的一个包装，有兴趣可以自己看看。

::::::info[可我用的是 C++98……]

<random> 在 C++11 中被加入，也就是说你无法在 C++98 或更老的标准中使用。

在 <tr1/random> 中笔者并没有找到 std::knuth_b 的替代品，不过大概率这玩意也没什么人用就是了。

::::::

__gnu_cxx::simd_fast_mersenne_twister_engine 系列

有关梅森旋转算法请见 std::mersenne_twister_engine 系列部分。

在 <ext/random> 中实现了 SIMD 优化的梅森旋转算法，包括基类 __gnu_cxx::simd_fast_mersenne_twister_engine 以及一众预定义的随机数生成器，包括从 __gnu_cxx::sfmt607、__gnu_cxx::sfmt1279 到 __gnu_cxx::sfmt216091 的数个生成器及其 _64 变种，具体有哪些详见 <ext/random>。

以 __gnu_cxx::sfmt19937 与 __gnu_cxx::sfmt19937_64 为例，与 std::mt19937 及 std::mt19937_64 相比，在笔者的电脑上生成相同数目随机数所用的时间近乎可以缩短一半，读者可自行尝试。

使用方法见 std::mersenne_twister_engine 系列部分，这里不再给出使用例。

::::::warning[很好，那我能用它吗？]{open}

大概率可行。

（个人觉得）

不过估计没有人试过在 NOIP 用这玩意。再加上它似乎和 SIMD SSE 啥的有关，跟指令集扯上干系可能会出事情。

不过在洛谷 IDE 上可以正常跑，而且速度能和 std::mt19937 及 std::mt19937_64 拉开很大。

如果有谁成功地在 NOI 系列赛事中使用 std::simd_fast_mersenne_twister_engine 系列，请联系笔者更新本部分。

::::::

::::::info[可我用的是 C++98……]

<ext/random> 在 C++11 中被加入，也就是说你无法在 C++98 或更老的标准中使用。

当前没有 <ext/random> 的替代品……老老实实地用 <tr1/random> 里的 std::tr1::mt19937 好了。

::::::

std::random_device

与上述其它随机数生成器不同，<random> 中的另一个随机数生成器 std::random_device 是非确定的，也就是其没有种子的概念，无法被预测。

::::::info[可我用的是 C++98……]{open}

<random> 在 C++11 中被加入，也就是说你无法在 C++98 或更老的标准中使用。

如果你迫切需要使用，你可以使用 <tr1/random> 替代，在其中定义了 std::tr1::random_device 以代替 std::random_device。详见 TR1 规范。

如果遇到这类情况，建议手动开启 C++11 或以上的语言标准进行评测。如果是在评测中出现的问题，可以尝试与教练交涉。

::::::

尽管 std::random_device 在不支持非确定随机数生成时，允许实现用伪随机数引擎实现，一般情况下其均由硬件随机数生成器生成。

::::::info[有意思的事情]

事实上，通过阅读 <tr1/random> 我们可以发现默认情况下 random_device 会尝试使用 urandom 作为随机数生成源，否则回退到 mt19937。

::::::

::::::warning[一件事情值得一提]

根据 CPPReference：

在 MinGW-w64 的旧版本中，std::random_device 为确定性的实现（漏洞 338，GCC 9.2 起修复）。

使用的时候要注意，尤其是如果电脑上还用着远古的 Bloodshed/Orwell Dev-C++ 配着 TDM-GCC 4.8.1。

::::::

在洛谷以及 NOI 评测环境所使用的 *nix 系统中，一般会使用真随机数生成器 /dev/urandom 作为其实现。

一般情况下，std::random_device 只用于伪随机数生成器的种子。

::::::info[不是为啥啊？]

参见 OI Wiki：

random_device 是一个基于硬件的均匀分布随机数生成器，在熵池耗尽前可以高速生成随机数。该类在 C++11 定义，需要 <random> 头文件。由于熵池耗尽后性能急剧下降，所以建议用此方法生成 mt19937 等伪随机数的种子，而不是直接生成。

说实话我其实不知道熵池是什么，不过既然 OI Wiki 都这么说了那应该就是了吧……（逃）

::::::

::::::warning[有些问题……]{open}

参见 OI Wiki：

random_device 是非确定的均匀随机位生成器，尽管若不支持非确定随机数生成，则允许实现用伪随机数引擎实现。目前笔者尚未接到报告称 NOIP 评测机不支持基于硬件的均匀分布随机数生成。

不过大概率是可行的。

不过上一句话是我说的。

::::::

随机数分布

显然，在大多数情况下，我们需要生成的是一定范围内的随机数，如上文中的使用例。

在 rand 函数的使用中一般使用 rand()%mod，而在 C++ 的随机数生成中一般使用随机数分布。

在 OI 中常用的一般就是 std::uniform_int_distribution，如下使用：

std::uniform_int_distribution<type> dis(l, r);

// 使用例
cout << dis(rd); // rd 为上文所述的随机数生成器

比如定义一个 [1, 100] 区间的 unsigned int 分布。

std::uniform_int_distribution<unsigned int> dis(1, 100) dis;

此外，较常见的还有 std::uniform_real_distribution，能生成一定区间内的浮点数。还有其它分布详见 CPPReference。

::::::info[可我用的是 C++98……]{open}

<random> 在 C++11 中被加入，也就是说你无法在 C++98 或更老的标准中使用。

如果你迫切需要使用，你可以使用 <tr1/random> 替代，在其中定义了 std::tr1::uniform_int 等预定义分布以替代 std::uniform_int_distribution 等分布。详见 TR1 规范。

如果遇到这类情况，建议手动开启 C++11 或以上的语言标准进行评测。如果是在评测中出现的问题，可以尝试与教练交涉。

::::::

不止于随机数生成！

现在我们已经有了一个能生成随机数的生成器，但是在实际情况下我们可能需要的并非从头生成一个序列，而是将一个序列随机打乱。

当然在这种情况下 C++ 已经为我们准备了一系列两个预制的函数。

std::random_shuffle

需要导入 <algorithm>。

::::::warning[还用这玩意？]{open}

自 C++14 起该函数已经被废弃，自 C++17 起该函数已经被删除。

如果不是题目要求，请尽可能避免使用本函数而转向使用下文中将会提到的 std::shuffle。

::::::

使用方式如下：

std::random_shuffle(first, last, myrand);

传入左闭右开的区间 [\text{first}, \text{last}) 与随机函数 myrand，其中 myrand 可省略。

值得一提的是，在 GCC 中 std::random_shuffle 如果没有传入 myrand 将会默认使用 rand 函数作为其随机数生成器。对的，就是 C 里面那个问题杂多的 rand 函数。

请尽量不要使用本函数，除非你被逼无奈。

::::::info[还有什么问题吗？]

有的兄弟。有的。

C++ 标准中要求 std::random_shuffle 在所有可能的排列中等概率随机选取。然而 GCC 并未严格按照这一标准实现。

原因在于上文所提到的 rand()%mod 的不均匀性和 RAND_MAX 的问题，总而言之就是 rand 太烂了。

因此在 C++14 与 C++17 两个标准中将这个函数果断抛弃也不是什么稀奇事了。

珍爱生命，远离 std::random_shuffle，无论你是出题的还是做题的。

::::::

std::shuffle

需要导入 <algorithm>，自 C++11 被加入。

使用方式如下：

std::shuffle(first, last, myrand);

传入左闭右开的区间 [\text{first}, \text{last}) 与随机数生成器 myrand（即 <random> 中定义的那些），其中 myrand 必须传入。

::::::info[可我用的是 C++98……]{open}

std::shuffle 在 C++11 中被加入，也就是说你无法在 C++98 或更老的标准中使用。

如果遇到这类情况，建议手动开启 C++11 或以上的语言标准进行评测。如果是在评测中出现的问题，可以尝试与教练交涉。

::::::

随机数种子

下面给出一些常见的随机数种子。

std::random_device

先用 std::random_device 生成一个随机数再用这个随机数作为其它随机数生成器的随机数种子。

time(nullptr)

::::::info[nullptr？]

一般情况下你可能会看到 time(0) 或者 time(NULL)，这同样可行。

nullptr 在 C++11 标准中加入作为 NULL 的替代，用以代表空指针。

以上三种写法中，time(0) 是在任何情况下均可行的，time(nullptr) 需要 C++11 及以上，而 time(NULL) 需要直接或间接导入以下几个头文件中的其中一个（此处引自 CPPReference）：

在标头 <clocale> 定义

在标头 <cstddef> 定义

在标头 <cstdio> 定义

在标头 <cstdlib> 定义

在标头 <cstring> 定义

在标头 <ctime> 定义

在标头 <cwchar> 定义

贵圈真乱.jpg

::::::

需要导入 <ctime>，是 C 标准库的遗老之一。

返回 UNIX 时间戳，即自 UTC 1970-01-01 00:00:00 起经过的秒数。

在 OI 评测中由于测试点经常会在同一秒内同时评测而导致随机数种子相同，不推荐在比赛中使用。

平常用用倒还可以。

std::chrono 系列。

包括 std::chrono::steady_clock::now().time_since_epoch().count()、std::chrono::system_clock::now().time_since_epoch().count() 与 std::chrono::high_resolution_clock::now().time_since_epoch().count()

真长。

自 C++11 起加入的时钟，需要导入 <chrono> 库。

这三个函数返回的时间单位为微秒或纳秒，精度如此之高，因此应当可以规避 time(nullptr) 的弊端。

其中，在笔者的 MinGW-w64 9.3.0 中，std::chrono::high_resolution_clock 是 std::chrono::system_clock 的别名。

更多信息详见 CPPReference。

例题

没有。

需要用到随机化的所有题都可以试试。

另请参阅

排序无先后之分。

大事记

2025.4.10 开始写初稿。

同日 推翻初稿，开始写二稿。

2025.4.11 想吃一中的米面。

2025.4.12 完成二稿。提交审核。

2025.4.13 继续完善二稿，增加数列打乱部分与 <tr1/random> 相关部分，重新交审。

写在本文后面

::::::info[有关本文 AI 使用的相关声明]{open}

在本文的实际创作前笔者使用了 ChatGLM 辅助进行信息搜索，但本文并未使用任何生成式人工智能（GenAI）参与本文的实际编写，包括但不限于使用生成式人工智能进行文本润色、文本编写、图片创作等。

上文中所提到的生成式人工智能包括但不限于 ChatGPT、Google Gemini、Claude、Grok、ChatGLM、Kimi、Minimax、Deepseek、Qwen 等。

:::::info[Fun Facts]

此处基本上我已经把我能想到的所有公开可用生成式 AI 丢进来了。

当然不包括我认为很烂的那些生成式 AI。

:::::

此处并没有广告。

::::::

::::::info[有关本文 AI 使用的相关声明（续）]

值得一提的是，在本文写作前笔者曾尝试使用过豆包进行信息搜索但随后发现其多次给出了错误的答案使本文被迫完全重写，在此对于豆包不表示任何感谢。

::::::