一些随机化技巧

异或哈希

常用于快速判断两个集合是否相等。

给每种元素设置一个随机的 unsigned long long 哈希值，每个集合的哈希值是其元素的哈希值的异或和。

例题：

• P8819 [CSP-S 2022] 星战
• 【2025暑期ACM04】图计算

Schwartz-Zippel 定理

对于一个域 $F$（通常为 $\text{mod}\, p$ 域，其中 $p$ 为大质数）下的 $m$ 元 $n$ 次多项式 $f(x_1,x_2,\dots,x_m)$，若每个 $x_i$ 均在 $F$ 中独立等概率随机，则 $f(x_1,x_2,\dots,x_m)=0$ 的概率 $\le \frac{n}{|F|}$。

感性理解，一元的情况下 $f$ 有 $n$ 个根，显然。

这个东西十分实用，常用于检验各种东西是否为 $0$（例如通过行列式快速检验积和式是否为 $0$）。

例题：

• P10102 [GDKOI2023 提高组] 矩阵

最大团的经典随机算法

随机一个加点顺序，按照这个顺序加点。若加进去后还是团则加进去，否则不加。这个东西实际上很难卡。

出现次数大于一半，每次随机化可以缩小一半错误率

例题：CF364D Ghd

练习：CF1305F Kuroni and the Punishment

颜色随机映射

处理类似于颜色两两不同的限制时，可以选取一个较小的 $m$ 并将颜色随机映射到 $[1,m]$，这样假设需要有 $k$ 个两两不同的颜色则正确率是 $\frac{m!}{(m-k)!m^k}$ 的。

例题：CF2003F Turtle and Three Sequences