随机化小结

交互中的随机暂时还没怎么做，等以后来总结。

我个人是比较认同 OI-wiki 对随机化技术的分类的，但是对于具体技术，这里不遵循 OI-wiki 的分类。

1 随机限制命中元素

经典应用有：3-SAT（通过随机添加限制，然后弱化到2-SAT解决

2 借助期望/概率

经典应用有：
1、随机游走的最大距离期望是根号级别，所以对于跟游走相关，而且没有顺序的 dp，可以考虑打乱后只跑 \(\sqrt n\) 以内。

2、对于 2n 个 01 变量，在 2^(2n) 中随机，随到恰好 n 个 1 的概率是 1/logn 级别。

3 整体探测法

4 随机染色法

这个大致可以分为 2 种，一种是把所有元素分为 0/1 两个集合，然后使用整体探测法，我在这里暂且称为 01染色，还有一种是把每个数字重新相互映射打乱一下，来防御特殊数据对某些 \(hash\) 的攻击。