Mivik
2021-01-21 09:43:07
随机，万恶之源。你做的题的数据多半是随机造的，也有能被随机乱搞过去的题，有的题标程就是随机，有的题就是出题人随机想到的 idea… 不得不说，OI 和随机还真扯不开关系。现在不妨让我们一起探索其不为大多数人所知的一面。
本文也在我的个人博客上发表
这里先给出一些下文会用到的定义：
均匀随机：一个随机变量
x 是均匀随机的当且仅当对于任何可能的取值v\in V 都有P(x=v)=\frac1{|V|} 。即每种情况出现的概率均等。单射：一个映射
f(x):X\rightarrow Y 是单射当且仅当不存在x,y\in X 使得x\ne y 且f(x)=f(y) 。满射：一个映射
f(x):X\rightarrow Y 是满射当且仅当对于任意y\in Y 都有x\in X 使得f(x)=y 。双射：一个映射
f(x):X\rightarrow Y 是双射当且仅当它既是单射又是满射。实际上简单地说就是X 中每一个元素和Y 中每一个元素一一对应。
在开始这场旅途之前，你或许需要一把引导你进入随机世界的钥匙：随机数。有了随机的整数，我们几乎可以生成任何随机目标。随机数的生成在 这篇洛谷日报 里面已经有过一些阐释，这里仅做一个简要的总结。
朴素地，你可以用 srand(seed) 来初始化伪随机数引擎，并使用 rand() 来生成一个值域为 [0,RAND_MAX] 的随机整数。但可惜的是，标准只要求了 RAND_MAX 至少为 32767，于是乎生成的整数有时并不能满足我们的需求。而且标准对 rand() 的实现没有具体要求，因此生产的循环数质量可能并不是很高（例如，有一定循环节）。因此 C++ 来救世了！
C++11（C++11！C++11！C++11！）提供了 random 库，可以在 cppreference 上查看详细。简要来说，它提供了许多可供选择的随机数生成引擎，其中最常用的应该是 std::mt19937 梅森旋转算法，它生成的随机数达到了 std::mt19937 的简单例子：
#include <iostream>
#include <random>
std::mt19937 engine(19260817);
int main() {
// 一个均匀随机的整数分布，使用方式为 dist(engine)
std::uniform_int_distribution<int> dist(0, 4);
int cnt[5] = { 0, 0, 0, 0, 0 };
for (int i = 0; i < 100000; ++i)
++cnt[dist(engine)];
for (int i = 0; i < 5; ++i)
std::cout << i << ": " << cnt[i] << std::endl;
}下面是在我电脑上运行一次的输出：
0: 20024
1: 19821
2: 20078
3: 20133
4: 19944可以看到分布是比较均匀的。但值得注意的是，mt19937 并不安全，也就是说攻击者可以根据 mt19937 的几个输出来推测出其内部状态，进而预测它的下一个输出。还可以参见我出的 这道题，大意为根据 mt19937 生成的随机数来反推初始化 mt19937 使用的种子。不过安全性似乎和 OIer 无关，我们就直接跳过吧。
C++11 的随机库好是好，但调用并不是很方便，这里先定义一些在下文会用到的辅助函数：
#include <chrono>
#include <random>
#include <type_traits>
// 使用当前时间初始化 mt19937
std::mt19937 engine(std::chrono::steady_clock::now().time_since_epoch().count());
template<class T, class = std::enable_if_t<std::is_integral_v<T>>> // 要求 T 必须为整型
T rand(T l, T r) {
return std::uniform_int_distribution(l, r)(engine);
}假设我们有一个数组，现在我们想要随机打乱它，并要求最后每一种排列出现的可能性相等，该怎么操作呢？
我一说，有些人啪就站起来了，说可以用 random_shuffle，很快啊！但是 random_shuffle 内部用的是 rand()，依然会有上面谈及的问题；C++11 推荐使用的是 std::shuffle(begin, end, engine)，使用随机数引擎来打乱数组。不过我们今天并不会浮于表面，我们来想想如何实现。
首先你有一个绝对能保证随机的算法：枚举出
for (int i = n - 1; i; --i)
std::swap(arr[i], arr[rand(0, i)]);没错，就这么简单。现在我们来证明一下为什么这个东西是均匀随机的。
我们考虑归纳证明。
void shuffle(int len) {
if (len == 1) return;
std::swap(arr[len - 1], arr[rand(0, len - 1)]);
shuffle(len - 1);
}然后我们现在假设这个算法能对长度为
又是一个常见的问题：你现在要从
实际上是有的。我们把上面那个洗牌算法下标反转一下，得到下面的算法：
for (int i = 0; i < n; ++i)
std::swap(arr[i], arr[rand(i, n - 1)]);然后我们发现，由于这个算法在
for (int i = 0; i < m; ++i)
std::swap(arr[i], arr[rand(i, n - 1)]);但是我们依旧需要一个长度为
我们想到，由于我们只会执行 unordered_map 记下除了前 swap 操作元素下标及其值，于是代码就变成了：
#include <cstdint>
#include <unordered_map>
#include <vector>
inline std::vector<uint64_t> select(uint64_t n, int m) {
std::unordered_map<uint64_t, uint64_t> rest;
uint64_t tmp[m];
for (uint64_t i = 0; i < m; ++i) tmp[i] = i + 1;
for (uint64_t i = 0; i < m; ++i) {
const uint64_t j = rand<uint64_t>(i, n - 1);
if (j < m) std::swap(tmp[i], tmp[j]);
else if (rest.find(j) == rest.end()) { // 没有找到
rest[j] = tmp[i];
tmp[i] = j + 1;
} else std::swap(tmp[i], rest[j]);
}
return std::vector<uint64_t>(tmp, tmp + m);
}（这里是为了方便理解，但是为了效率肯定还是要把那个 find 返回的迭代器存下来的，否则会多一次 find 的过程）
这样 unordered_map 中最多只会加入
OI 出题中常常遇到这样的需求：单个数据点范围没有限制，但是所有数据点的总和有限制，这时我们需要把一个大数
由于大数划分的方案和我们这个选点的方案一一对应形成双射，所以可以证得我们的方案生成是均匀随机的。
#include <cassert>
#include <type_traits>
#include <vector>
template<class T, class = std::enable_if_t<std::is_integral_v<T>>>
inline std::vector<T> partition(T sum, T count) {
assert(sum >= 0 && count > 0);
const T len = sum + count - 1;
auto ps = choose<T>(0, len - 1, count - 1);
std::sort(ps.begin(), ps.end());
std::vector<T> ret; ret.resize(count);
T last = 0;
for (size_t i = 0; i < ps.size(); ++i) {
ret[i] = ps[i] - last;
last = ps[i] + 1;
}
ret.back() = len - last;
return ret;
}这样生成的数下界是
#include <cassert>
#include <type_traits>
#include <vector>
template<class T, class = std::enable_if_t<std::is_integral_v<T>>>
inline std::vector<T> partition(T sum, T count, T min_value = 1) {
if (min_value < 0) min_value = 0;
assert(sum >= 0 && count > 0);
assert(min_value * count <= sum);
const T len = sum + count * (1 - min_value) - 1;
auto ps = choose<T>(0, len - 1, count - 1);
std::sort(ps.begin(), ps.end());
std::vector<T> ret; ret.resize(count);
T last = 0;
for (size_t i = 0; i < ps.size(); ++i) {
ret[i] = ps[i] - last + min_value;
last = ps[i] + 1;
}
ret.back() = len - last + min_value;
return ret;
}不过带上界的序列均匀随机划分我个人目前还没有找到什么办法… 如果有知道的可以联系我，QQ 洛谷均可，谢谢啦~
我们如下递归定义合法的括号序列：
A 是合法的括号序列，那么 (A) 和 A() 也是合法的括号序列众所周知，长度为
下文在数学公式中用到左右括号的地方都会用下划线表示来与数学中的括号区分。
我们首先来给出几个定义。一个括号序列是平衡的，当且仅当其中的左括号和右括号一样多。为了方便理解，我们先把一个长度为
然后我们定义一个平衡括号序列 flaw）为
我们定义如果
引理 1：一个平衡括号序列
w 有且仅有一种分解w=w_1w_2w_3\cdots w_k ，其中w_i （1\le i\le k ）为不可约的平衡括号序列。
记
我们首先找到一个非空的平衡合法括号序列
定理 1：
\Phi(w) 建立了从B_n 到B_{n,0} 的映射。
也就是说
定理 2：
\Phi(w) 对于任意0\le k\le n 建立了B_{n,k} 到B_{n,0} 的单射。
假设存在两个不相等的平衡括号序列
综上，我们得证。
定理 3：
\Phi(w) 对于任意0\le k\le n 建立了B_{n,k} 到B_{n,0} 的双射。
结合定理 2 和单射的性质我们知道
由于
出现矛盾，假设不成立。因此对于任何
接下来就很愉快啦～我们只需要随机生成一个平衡括号序列（即在
#include <algorithm>
#include <string>
#include <map>
inline std::string brackets(size_t n) {
const size_t len = n << 1;
bool arr[len];
std::fill(arr, arr + n, 1);
std::fill(arr + n, arr + len, 0);
std::shuffle(arr, arr + len, engine);
size_t start = 0, end = len;
while (true) {
size_t lef_count = 0, rig_count = 0;
bool ok = true;
for (size_t i = start, j; i < end; ++i) {
++(arr[i]? rig_count: lef_count);
if (lef_count >= rig_count) continue;
for (j = i + 1; j < end; ++j) {
++(arr[j]? rig_count: lef_count);
if (rig_count > lef_count) continue;
// ( ) ) ) ) ( ( ( ) ) ) ( ( (
// i ---S--- j -----T-----
// we swap S and T and then flip S, i and j
const size_t len = j - i - 1;
std::rotate(arr + i + 1, arr + j + 1, arr + end);
std::copy_backward(arr + end - len - 1, arr + end - 1, arr + end);
std::transform(arr + end - len, arr + end, arr + end - len, std::logical_not());
arr[i] = 0; arr[end - len - 1] = 1;
start = i + 1; end = end - len - 1;
ok = false;
break;
}
}
if (ok) break;
}
std::string ret; ret.resize(len);
for (size_t i = 0; i < len; ++i) ret[i] = "()"[arr[i]];
return ret;
}
int main() {
// 验证均匀随机性
std::map<std::string, int> rec;
const int n = 4, T = 100000;
for (int i = 0; i < T; ++i)
++rec[brackets(n)];
for (auto &[str, cnt] : rec)
std::cout
<< str << ": "
<< ((double)cnt / T) << std::endl;
}下面是在我电脑上运行一次的输出：
(((()))): 0.07066
((()())): 0.07385
((())()): 0.07146
((()))(): 0.0732
(()(())): 0.07022
(()()()): 0.06976
(()())(): 0.07197
(())(()): 0.07146
(())()(): 0.0715
()((())): 0.07129
()(()()): 0.07212
()(())(): 0.07061
()()(()): 0.07121
()()()(): 0.07069可以看到还是分布得很均匀的。
注意这里的二叉树是有根的。
定理 4：所有
n 个结点的有根二叉树形成的集合与B_{n,0} 构成双射。
首先我们直到