随机化技巧 - 杂项

author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ

## 概述

前置知识： [随机函数](/misc/random/) 和 [概率初步](/math/expectation/)

本文将对 OI/ICPC 中的随机化相关技巧做一个简单的分类，并对每个分类予以介绍。本文也将介绍一些在 OI/ICPC 中很少使用，但与 OI/ICPC 在风格等方面较为贴近的方法，这些内容前将用 `(*)` 标注。

这一分类并不代表广泛共识，也必定不能囊括所有可能性，因此仅供参考。

**记号和约定** ：

-	$\mathrm{Pr}[A]$ 表示事件 $A$ 发生的概率。
-	$\mathrm{E}[X]$ 表示随机变量 $X$ 的期望。
- 赋值号 $:=$ 表示引入新的量，例如 $Y:=1926$ 表示引入值为 $1926$ 的量 $Y$ 。

## 用随机集合覆盖目标元素

庞大的解空间中有一个（或多个）解是我们想要的。我们可以尝试进行多次撒网，只要有一次能够网住目标解就能成功。

### 例：三部图的判定

###+ note "问题"
> 给定一张 $n$ 个结点、 $m$ 条边的简单无向图，用 RGB 三种颜色给每个结点染色 满足任意一对邻居都不同色，或者报告无解。

对每个点 $v$ ，从 $\\{R,G,B\\}$ 中等概率独立随机地选一种颜色 $C_v$ ，并钦定 $v$	**不** 被染成 $C_v$ 。最优解恰好符合这些限制的概率，显然是 $\big(\frac 23\big)^n$ 。

在这些限制下，对于一对邻居 $(u,v)$ ，“ $u,v$ 不同色”的要求等价于以下这条“推出”关系：

- 对于所有异于 $C_u,C_v$ 的颜色 $X$ ，若 $u$ 被染成 $X$ ，则 $v$ 被染成 $\\{R,G,B\\}\setminus\\{X,C_v\\}$ 。

于是我们可以对每个 $v$ 设置布尔变量 $B_v$ ，其取值表示 $v$ 被染成两种剩余的颜色中的哪一种。借助 2-SAT 模型即可以 $O(n+m)$ 的复杂度解决这个问题。

这样做，单次的正确率是 $\big(\frac 23\big)^n$ 。将算法重复运行 $-\big(\frac 32\big)^n\log \epsilon$ 次，只要有一次得到解就输出，这样即可保证 $1-\epsilon$ 的正确率。（详见后文中“自然常数的使用”和“抽奖问题”）

* * *

**回顾** ：本题中“解空间”就是集合 $\\{R,G,B\\}^n$ ，我们每次通过随机施加限制来在一个缩小的范围内搜寻“目标解”——即合法的染色方案。

### 例： [CodeChef SELEDGE](https://www.codechef.com/problems/SELEDGE)

###+ note "简要题意"
> 给定一张点、边都有非负权值的无向图，找到一个大小 $\leq K$ 的边集合 $S$ ，以最大化与 $S$ 相连的点的权值和减去 $S$ 的边权和。一个点的权值只被计算一次。

观察：如果选出的边中有三条边构成一条链，则删掉中间的那条一定不劣；如果选出的边中有若干条构成环，则删掉任何一条一定不劣。

推论：最优解选出的边集，一定构成若干个不相交的菊花图（即直径不超过 2 的树）。

推论：最优解选出的边集，一定构成一张二分图。

我们对每个点等概率独立随机地染上黑白两种颜色之一，并要求这一染色方案，恰好也是最优解所对应的二分图的黑白染色方案。

尝试计算最优解符合这一要求的概率：

- 考虑一张 $n$ 个点的菊花图，显然它有 2 种染色方案，所以它被染对颜色的概率是 $\dfrac 2{2^n}=2^{1-n}$ 。
- 假设最优解中每个菊花的结点数分别为 $a_1,\cdots,a_l$ ，则一定有 $(a_1-1)+\cdots+(a_l-1)\leq K$ ，其中 $K$ 表示最多能够选出的边数。
- 从而所有菊花都被染对颜色的概率是 $2^{1-a_1}\cdots 2^{1-a_l}\geq 2^{-K}$ 。

在上述要求下，尝试建立费用流模型计算最优答案：

-	 建立二分图，白点在左侧并与 $S$ 相连，黑点在右侧并与 $T$ 相连。
> - 对于白点 $v$ ，从 $S$ 向它连一条容量为 1、费用为 $-A_v$ 的边，和一条容量为 $\infty$ 、费用为 0 的边。
> - 对于黑点 $v$ ，从它向 $T$ 连一条容量为 1、费用为 $-A_v$ 的边，和一条容量为 $\infty$ 、费用为 0 的边。
- 对于原图中的边 $(u,v,B)$ 满足 $u$ 为白色、 $v$ 为黑色，连一条从 $u$ 到 $v$ 的边，容量为 1，费用为 $B$ 。
- 在该图中限制流量不超过 $K$ ，则最小费用的相反数就是答案。

用 SPFA 费用流求解的话，复杂度是 $O\big(K^2(n+m)\big)$ ，证明：

- 首先，显然 SPFA 的运行次数 $\leq K$ 。
-	 然后，在一次 SPFA 中，任何一个结点至多入队 $O(K)$ 次。这是因为：
> - 任意时刻有流量的边不会超过 $3K$ 条，否则就意味着在原图中选了超过 $K$ 条边。
> - 对于任何一条长为 $L$ 的增广路，其中至少有 $\dfrac L2-2$ 条边是某条有流量的边的反向边，因为正向边都是从图的左侧指向右侧，只有这些反向边才会从右侧指向左侧。
> - 综合以上两条，得到任意一条增广路的长度不超过 $6K+4$ 。
- 综上，复杂度是 $O\big(K^2(n+m)\big)$ 。

和上一题类似，我们需要把整个过程重复 $-2^K \log\epsilon$ 次以得到 $1-\epsilon$ 的正确率。总复杂度 $O\big(2^KK^2(n+m)\cdot -\log\epsilon\big)$ 。

## 用随机元素命中目标集合

我们需要确定一个集合中的任意一个元素，为此我们随机选取元素，以期能够恰好命中这一集合。

### 例： [Gym 101550I](https://codeforces.com/gym/101550/attachments)

###+ note "简要题意"
> 有一张图形如：两条平行的链，加上连接两链的两条平行边。给定这张图上的若干条简单路径（每条路径表示一次通话），请你选择尽量少的边放置窃听器，以使得每条给定的路径上都有至少一个窃听器。

整张图可以拆分为一个环加上四条从环伸出去的链。对于这四条链中的任何一条（记作 $C$ ），考虑在这条链上如何放置窃听器，容易通过贪心算法得到满足以下条件的方案：

- 在拦截所有 $C$ 内部进行的通话的前提下，用的窃听器数量最少。
-	 在上一条的前提下，使得 $C$ 上的窃听器离环的最短距离尽可能小。
> - 作这一要求的目的是尽可能地拦截恰有一个端点在 $C$ 内部的通话。

接着考虑链与环相接处的共计 4 条边，我们暴力枚举这些边上有没有放窃听器。显然，如果想要拦截跨越链和环的通话，在这 4 条边上放窃听器一定是最优的。现在，我们可以把通话线路分为以下几种：

1. 完全在链上的通话线路。这些线路一定已经被拦截，故可以忽略。
2. 跨越链和环，且已经被拦截的通话线路。它们可以忽略。
3. 跨越链和环，且未被拦截的通话线路。我们可以直接截掉它在链上的部分（因为链上的窃听器放置方案已经固定了），只保留环上的部分。
4. 完全在环上的通话线路。

至此，问题转化成了环上的问题。

设最优解中在环上的边集 $S$ 上放置了窃听器，如果我们已经确定了 $S$ 中的任何一个元素 $e$ ，就可以：

- 先在 $e$ 处断环为链。
- 然后从 $e$ 开始贪心，不断找到下一个放置窃听器的边。注意到如果经过合适的预处理，贪心的每一步可以做到 $O(1)$ 的复杂度。
- 从而以 $O(|S|)$ 的复杂度解决问题。

我们考虑随机选取环上的一条边 $e'$ ，并钦定 $e'\in S$ 再执行上述过程，重复多次取最优。

分析单次复杂度：

- 观察：记 $S'$ 表示所有选取了 $e'$ 的方案中的最优解，则 $|S'|\leq |S|+1$ 。
- 从而单次复杂度 $O(|S'|)=O(|S|)$ 。

分析正确率：

- 显然单次正确率 $\dfrac {|S|}n$ ，其中 $n$ 表示环长。
- 所以需要重复 $-\dfrac n{|S|}\log\epsilon$ 次以得到 $1-\epsilon$ 的正确率。

综上，该算法的复杂度 $O\big(|S|\cdot -\dfrac n{|S|}\log\epsilon\big)=O(-n\log\epsilon)$ 。

### 例： [CSES 1685 New Flight Routes](https://cses.fi/problemset/task/1685)

###+ note "简要题意"
> 给定一张有向图，请你加最少的边使得该图强连通，需 **输出方案** 。

先对原图进行强连通缩点。我们的目标显然是使每个汇点能到达每个源点。

不难证明，我们一定只会从汇点到源点连边，因为任何其他的连边，都能对应上一条不弱于它的、从汇点到源点的连边。

我们的一个核心操作是，取汇点 $t$ 和源点 $s$ （它们不必在同一个弱连通分量里），连边 $t\to s$ 以 **使得 $s$ 和 $t$ 都不再是汇点或源点** （记作目标 I）。理想情况下这种操作每次能减少一个汇点和一个源点，那我们不断操作直到只剩一个汇点或只剩一个源点，而这样的情形就很平凡了。由此，我们猜测答案是源点个数与汇点个数的较大值。

不难发现，上述操作能够达到目标 I 的充要条件是： $t$ 拥有 $s$ 以外的前驱、且 $s$ 拥有 $t$ 以外的后继。可以证明（等会会给出证明），对于任意一张有着至少两个源点和至少两个汇点的 DAG，都存在这样的 $(s,t)$ ；但存在性的结论无法帮助我们构造方案，还需做其他分析。

- 有了这个充要条件还难以直接得到算法，主要的原因是连边 $t\to s$ 后可能影响其他 $(s',t')$ 二元组的合法性，这个比较难处理。

注意到我们关于源汇点间的关系知之甚少（甚至连快速查询一对 $s-t$ 间是否可达都需要 dfs + bitset 预处理，而时限并不允许这么做），这提示我们需要某种非常一般和强大的性质。

观察：不满足目标 I 的 $(s,t)$ 至多有 $n+m-1$ 对，其中 $n$ 表示源点个数， $m$ 表示汇点个数。

- 理由：对于每一对这样的 $(s,t)$ ，若把它看成 $s,t$ 间的一条边，则所有这些边构成的图形如若干条不相交的链，于是边数不超过点数减一。
- 作出这一观察的动机是，要想将存在性结论应用于算法，前置步骤往往是把定性的结果加强为定量的结果。

推论：等概率随机选取 $(s,t)$ ，满足前述要求的概率 $\geq \dfrac {(n-1)(m-1)}{nm}$ 。

- 注意到这个结论严格强于先前给出的存在性结论。

推论：等概率独立随机地连续选取 $\dfrac {\min(n,m)}2$ 对不含公共元素的 $(s,t)$ ，并对它们 **依次** 操作（即连边 $t\to s$ ），则这些操作全部满足目标 I 的概率 $\geq \dfrac 14$ 。

- 理由：

$$
\begin{aligned}
&\phantom{=\ }\dfrac {(n-1)(m-1)}{nm}\cdot\dfrac{(n-2)(m-2)}{(n-1)(m-1)}\cdots\dfrac{(n-k)(m-k)}{(n-k+1)(m-k+1)}\\\\
&=\dfrac{(n-k)(m-k)}{nm}\\\\
&\geq \dfrac 14
\end{aligned}
$$

而连续选完 $k$ 对 $(s,t)$ 后判断它们是否全部满足目标 I 很简单，只要再跑一遍强连通缩点，判断一下 $n,m$ 是否都减小了 $k$ 即可。注意到若每次减少 $k=\dfrac{\min(n,m)}2$ ，则 $\min(n,m)$ 必在 $O\big(\log(n+m)\big)$ 轮内变成 1，也就转化到了平凡的情况。

###+ note "算法伪代码"
```text
		while(n>1 and m>1):
				randomly choose k=min(n,m)/2 pairs (s,t)
				add edge t->s for all these pairs
				if new_n>n-k or new_m>m-k:
						roll_back()
		solve_trivial()
```

复杂度 $O\big((|V|+|E|) \log |V|\big)$ 。

* * *

**回顾** ：我们需要确定任意一对能够实现目标 I 的二元组 $(s,t)$ ，为此我们随机选择 $(s,t)$ 。

## 用随机化获得随机数据的性质

如果一道题的数据随机生成，我们可能可以利用随机数据的性质解决它。而在有些情况下，即使数据并非随机生成，我们也可以通过随机化来给其赋予随机数据的某些特性，从而帮助解决问题。

### 例：随机增量法

随机生成的元素序列可能具有“前缀最优解变化次数期望下很小”等性质，而随机增量法就通过随机打乱输入的序列来获得这些性质。

详见 [随机增量法](/geometry/random-incremental/) 。

### 例： [TopCoder MagicMolecule](https://community.topcoder.com/stat?c=problem_statement&pm=11705) 随机化解法

###+ note "简要题意"
> 给定一张 $n$ 个点、带点权的无向图，在其中所有大小不小于 $\dfrac {2n}3$ 的团中，找到点权和最大的那个。
> 
>	$n\leq 50$

不难想到折半搜索。把点集均匀分成左右两半 $V_L,V_R$ （大小都为 $\dfrac n2$ ），计算数组 $f_{L,k}$ 表示点集 $L\subseteq V_L$ 中的所有 $\geq k$ 元团的最大权值和。接着我们枚举右半边的每个团 $C_R$ ，算出左半边有哪些点与 $C_R$ 中的所有点相连（这个点集记作 $N_L$ ），并用 $f_{N_L,\frac 23 n-|C_R|}+\textit{value}(C_R)$ 更新答案。

-	 注意到可以 $O(1)$ 转移每一个 $f_{L,k}$ 。具体地说，取 $d$ 为 $L$ 中的任意一个元素，然后分类讨论：
> - 假设最优解中 $d$ 不在团中，则从 $f_{L\setminus \\{d\\},k}$ 转移而来。
> - 假设最优解中 $d$ 在团中，则从 $f_{L\cap N(d),k}+\textit{value}(d)$ 转移而来，其中 $N(d)$ 表示 $d$ 的邻居集合。
> - 别忘了还要用 $f_{L,k+1}$ 来更新 $f_{L,k}$ 。

这个解法会超时。尝试优化：

-	 平分点集时均匀随机地划分。这样的话，最优解的点集 $C_{res}$ 以可观的概率也被恰好平分（即 $|C_{res}\cap V_L|=|C_{res}\cap V_R|$ ）。
> - 当然， $|C_{res}|$ 可能是奇数。简单起见，这里假设它是偶数；奇数的情况对解法没有本质改变。
> - 实验发现，随机尝试约 20 次就能以很大概率有至少一次满足该性质。也就是说，如果我们的算法依赖于“ $C_{res}$ 被平分”这一性质，则将算法重复执行 20 次取最优，同样也能保证以很大概率得到正确答案。
-	 有了这一性质，我们就可以直接钦定左侧团 $L$ 、右侧团 $C_R$ 的大小都 $\geq \dfrac n3$ 。这会对复杂度带来两处改进：
> -	$f$ 可以省掉记录大小的维度。
> - 因为只需考虑大小 $\geq \dfrac n3$ 的团，所以需要考虑的左侧团 $L$ 和 右侧团 $C_R$ 的数量也大大减少至约 $1.8\cdot 10^6$ 。
-	 现在的瓶颈变成了求单侧的某一子集的权值和，因为这需要 $O\big(2^{|V_L|}+2^{|V_R|}\big)$ 的预处理。
> - 解决方案：在 $V_L,V_R$ 内部再次折半；当查询一个子集的权值和时，将这个子集分成左右两半查询，再把答案相加。
- 这样即可通过本题。

* * *

**回顾** ：一个随机的集合有着“在划分出的两半的数量差距不会太悬殊”这一性质，而我们通过随机划分获取了这个性质。

## 随机化用于哈希

### 例： [UOJ #207 共价大爷游长沙](https://uoj.ac/problem/207)

###+ note "简要题意"
> 维护一棵动态变化的树，和一个动态变化的结点二元组集合。你需要支持：
> 
> - 删边、加边。保证得到的还是一棵树。
> - 加入/删除某个结点二元组。
> - 给定一条边 $e$ ，判断是否对于集合中的每个结点二元组 $(s,t)$ ， $e$ 都在 $s,t$ 间的简单路径上。

对图中的每条边 $e$ ，我们定义集合 $S_e$ 表示经过该边的关键路径（即题中的 $(a,b)$ ）集合。考虑对每条边动态维护集合 $S_e$ 的哈希值，这样就能轻松判定 $S_e$ 是否等于全集（即 $e$ 是否是“必经之路”）。

哈希的方式是，对每个 $(a,b)$ 赋予 $2^{64}$ 以内的随机非负整数 $H_{(a,b)}$ ，然后一个集合的哈希值就是其中元素的 $H$ 值的异或和。

这样的话，任何一个固定的集合的哈希值一定服从 $R:=\big\\{0,1,\cdots,2^{64}-1\big\\}$ 上的均匀分布（换句话说，哈希值的取值范围为 $R$ ，且取每一个值的概率相等）。这是因为：

1. 单个 $H_{(a,b)}$ 显然服从均匀分布。
2. 两个独立且服从 $R$ 上的均匀分布的随机变量的异或和，一定也服从 $R$ 上的均匀分布。自证不难。

从而该算法的正确率是有保障的。

至于如何维护这个哈希值，使用 LCT 即可。

### 例： [CodeChef PANIC](https://www.codechef.com/problems/PANIC) 及其错误率分析

本题的大致解法：

1. 可以证明[^ref1] $S(N)$ 服从一个关于 $N$ 的 $O(K)$ 阶线性递推式。
2. 用 BM 算法求出该递推式。
3. 借助递推式，用凯莱哈密顿定理计算出 $S(N)$ 。

这里仅关注第二部分，即如何求一个矩阵序列的递推式。所以我们只需考虑下述问题：

###+ note "问题"
> 给定一个矩阵序列，该序列在模 $P:=998244353$ 意义下服从一个齐次线性递推式（递推式中的数乘和加法运算定义为矩阵的数乘和加法），求出最短递推式。

如果一系列矩阵服从一个递推式 $F$ ，那么它的每一位也一定服从 $F$ 。然而，如果对某一位求出最短递推式 $F'$ ，则 $F'$ 可能会比 $F$ 更短，从而产生问题。

解决方案：给矩阵的每一位 $(i,j)$ 赋予一个 $<P$ 的随机权值 $x_{i,j}$ ，然后对于序列中每个矩阵计算其所有位的加权和模 $P$ 的结果，再把每个矩阵算出的这个数连成一个数列，最后我们对所得数列运行 BM 算法。

错误率分析：

- 假设上述做法求得了不同于 $F$ （且显然也不长于 $F$ ）的 $l$ 阶递推式 $F'$ 。
- 因为矩阵序列不服从 $F'$ ，所以一定存在矩阵中的某个位置 $(i,j)$ ，满足该位置对应的数列 $S_{i,j}$ 在某个 $N$ 处不服从 $F'$ 。也就是说：

$$
S(N)_{i,j}-F'_1S(N-1)_{i,j}-\cdots-F'_lS(N-l)_{i,j}\not\equiv 0\pmod {P}
$$

- 假设 $(i,j)$ 是唯一的不服从的位置，则一定有：

$$
T_{i,j}:=\Big(x_{i,j}\cdot\big(S(N)_{i,j}-F'_1S(N-1)_{i,j}-\cdots-F'_lS(N-l)_{i,j}\big)\bmod P\Big)=0
$$

- 显然这仅当 $x_{i,j}=0$ 时才成立，概率 $P^{-1}$ 。
-	 如果有多个不服从的位置呢？
> - 对每个这样的位置 $(i,j)$ ，易证 $T_{i,j}$ 服从 $R:=\\{0,1,\cdots,P-1\\}$ 上的均匀分布。
> - 若干个互相独立的、服从 $R$ 上的均匀分布的随机变量，它们在模意义下的和，依然服从 $R$ 上的均匀分布。自证不难。
> - 从而这种情况下的错误率也是 $P^{-1}$ 。

### 例： [UOJ #552 同构判定鸭](https://uoj.ac/problem/552) 及其错误率分析

###+ note "简要题意"
> 给定两张边权为小写字母的有向图 $G_0,G_1$ ，你要对这两张图分别算出「所有路径对应的字符串构成的多重集」（可能是无穷集），并判断这两个多重集是否相等。如果不相等，你要给出一个最短的串，满足它在两个多重集中的出现次数不相等。

令 $f_{K,i,j}$ 表示图 $G_K$ 中从点 $i$ 开始的所有长为 $j$ 的路径，这些路径对应的所有字符串构成的多重集的哈希值。按照 $j$ 升序考虑每个状态，转移时枚举 $i$ 的出边并钦定该边为路径上的第一条边。

要判断是否存在长度 $=L$ 的坏串，只需把 $\\{f_{0,*,L}\\}$ 和 $\\{f_{1,*,L}\\}$ 各自“整合”起来再比较即可（通配符 `*` 这里表示每一个结点，例如 $\\{f_{0,*,L}\\}$ 表示全体 $f_{0,i,L}$ 构成的集合，其中 $i$ 取遍所有结点）。官方题解[^ref2]中证明了最短坏串（如果存在的话）长度一定不超过 $n_1+n_2$ ，所以这个解法的复杂度是可靠的。

接下来考虑具体的哈希方式。注意到常规的哈希方法——即把串 $a_1a_2\cdots a_k$ 映射到 $\big(a_1+Pa_2+P^2a_3+\cdots+P^{k-1}a_k\big)\bmod Q$ 上、再把多重集的哈希值定为其中元素的哈希值之和模 $Q$ ——在这里是行不通的。一个反例是，集合 `{"ab","cd"}` 与集合 `{"cb","ad"}` 的哈希值是一样的，不论 $P,Q$ 如何取值。

上述做法的问题在于，一个串的哈希值是一个和式，从而其中的每一项可以拆出来并重组。为避免这一问题，我们考虑把哈希值改为一个连乘式。此外，乘法交换律会使得不同的位不可区分，为避免这一点我们要为不同的位赋予不同的权值。

对每一个二元组 $(c,j)$ （其中 $c$ 为字符， $j$ 为整数表示 $c$ 在某个串中的第几位）我们都预先生成一个随机数 $x_{c,j}$ 。然后我们把串 $a_1a_2\cdots a_k$ 映射到 $x_{a_1,1}x_{a_2,2}\cdots x_{a_k,k}\bmod Q$ 上（其中 $Q$ 为 **随机选取** 的质数）、再把多重集的哈希值定为其中元素的哈希值之和模 $Q$ 。接下来分析它的错误率。

###+ note "(\*)Schwartz-Zippel 引理"
> 令 $f\in F[z_1,\cdots,z_k]$ 为域 $F$ 上的 $k$ 元 $d$ 次非零多项式，令 $S$ 为 $F$ 的有限子集，则至多有 $d\cdot |S|^{k-1}$ 组 $(z_1,\cdots,z_k)\in S^k$ 满足 $f(z_1,\cdots,z_k)=0$ 。
> 
> ### mdui-shadow-6 "如果你不知道域是什么"
>		 你只需记得这两样东西都是域：
> 
>		 1. 模质数的剩余系，以及其上的各种运算。
>		 2. 实数集，以及其上的各种运算。
> 
> 推论：若 $z_1,\cdots,z_k$ 都在 $S$ 中等概率独立随机选取，则 $\mathrm{Pr}\big[f(z_1,\cdots,z_k)=0\big]\leq \dfrac d{|S|}$ 。

记 $F$ 为模 $Q$ 的剩余系所对应的域，则对于一个 $L\leq n_1+n_2$ ， $\sum\limits_i f_{0,i,L}$ 和 $\sum\limits_i f_{1,i,L}$ 就分别对应着一个 $F$ 上关于变元集合 $\\{x_{*,*}\\}$ 的 $L$ 次多元多项式，不妨将这两个多项式记为 $P_0,P_1$ 。

假如两个不同的字符串多重集的哈希值相同，则有两种可能：

1.	$P_0\equiv P_1\pmod {Q}$ ，即 $P_0,P_1$ 的每一项系数在模 $Q$ 意义下都对应相等。
2.	$P_0\not\equiv P_1\pmod {Q}, P_0(x_{*,*})\equiv P_1(x_{*,*})\pmod {Q}$ ，即 $P_0,P_1$ 虽然不恒等，但我们选取的这一组 $\\{x_{*,*}\\}$ 恰好使得它们在此处的点值相等。

分析前者发生的概率：

- 观察：对于任意的 $A\neq B; A,B\leq N$ 和随机选取的质数 $Q\leq Q_{max}$ ，一定有：

$$
\mathrm{Pr}\big[A\equiv B\pmod {Q}\big]=O\Big(\dfrac{\log N \log Q_{max}}{Q_{max}}\Big)
$$

- 这是因为：使 $A\equiv B$ 成立的 $Q$ 一定满足 $Q\big|(A-B)$ ，这样的 $Q$ 有 $\omega(A-B)\leq \log_2 N$ 个；而由质数定理， $Q_{max}$ 以内不同的质数又有 $\Theta\Big(\dfrac {Q_{max}}{\log Q_{max}}\Big)$ 个。将两者相除即可得到上式。
- 在上述观察中取 $A,B$ （满足 $A\neq B$ ）为某一特定项在 $P_0,P_1$ 中的系数（也就等于该项对应的串在 $G_0,G_1$ 中的出现次数），则易见 $A,B\leq (m_1+m_2)^{L}$ ，得到：

$$
\mathrm{Pr}\big[A\equiv B\pmod {Q}\big]=O\Big(\dfrac{L\log (m_1+m_2) \log Q_{max}}{Q_{max}}\Big)
$$

- 所以取 $Q_{max}\approx 10^{12}$ 就绰绰有余。如果机器无法支持这么大的整数运算，可以用双哈希代替。

分析后者发生的概率：

-	 在 Schwartz-Zippel 引理中：
> - 取域 $F$ 为模 $Q$ 的剩余系对应的域
> - 取 $f(x_{*,*})=P_0(x_{*,*})-P_1(x_{*,*})$ 为 $L$ 次非零多项式
> - 取 $S=F$ 
- 得到：所求概率 $\leq \dfrac LQ$ 。

注意到我们需要对每个 $L$ 都能保证正确性，所以要想保证严谨的话还需用 Union Bound（见后文）说明一下。

实践上我们不必随机选取模数，因为——比如说——用自己的生日做模数的话，实际上已经相当于随机数了。

### 例：(\*）子矩阵不同元素个数

###+ note "问题"
> 给定 $n\times m$ 的矩阵， $q$ 次询问一个连续子矩阵中不同元素的个数，要求在线算法。
> 
> 允许 $\epsilon$ 的相对误差和 $\delta$ 的错误率，换句话说，你要对至少 $(1-\delta)q$ 个询问给出离正确答案相对误差不超过 $\epsilon$ 的回答。
> 
>	$n\cdot m\leq 2\cdot10^5;q\leq 10^6;\epsilon=0.5,\delta=0.2$

引理：令 $X_{1\cdots k}$ 为互相独立的随机变量，且取值在 $[0,1]$ 中均匀分布，则 $\mathrm{E}\big[\min\limits_i X_i\big]=\dfrac 1{k+1}$ 。

- 证明：考虑一个单位圆，其上分布着 **相对位置** 均匀随机的 $k+1$ 个点，分别在位置 $0,X_1,X_2,\cdots,X_k$ 处。那么 $\min\limits_i X_i$ 就等于 $k+1$ 段空隙中特定的一段的长度。而因为这些空隙之间是“对称”的，所以其中任何一段特定空隙的期望长度都是 $\dfrac 1{k+1}$ 。

我们取 $k$ 为不同元素的个数，并借助上述引理来从 $\min\limits_i X_i$ 反推得到 $k$ 。

考虑采用某个哈希函数，将矩阵中每个元素都均匀、独立地随机映射到 $[0,1]$ 中的实数上去，且相等的元素会映射到相等的实数。这样的话，一个子矩阵中的所有元素对应的那些实数，在去重后就恰好是先前的集合 $\\{X_1,\cdots,X_k\\}$ 的一个实例，其中 $k$ 等于子矩阵中不同元素的个数。

于是我们得到了算法：

1. 给矩阵中元素赋 $[0,1]$ 中的哈希值。为保证随机性，哈希函数可以直接用 `map` 和随机数生成器实现，即每遇到一个新的未出现过的值就给它随机一个哈希值。
2. 回答询问时设法求出子矩阵中哈希值的最小值 $M$ ，并输出 $\dfrac 1M-1$ 。

然而，这个算法并不能令人满意。它的输出值的期望是 $\mathrm{E}\Big[\dfrac 1{\min\limits_i X_i}-1\Big]$ ，但事实上这个值并不等于 $\dfrac 1{\mathrm{E}\big[\min\limits_i X_i\big]}-1=k$ ，而（可以证明）等于 $\infty$ 。

也就是说，我们不能直接把 $\min\limits_i X_i$ 的单次取值放在分母上，而要先算得它的期望，再把期望值放在分母上。

怎么算期望值？多次随机取平均。

我们用 $C$ 组不同的哈希函数分别执行前述过程，回答询问时计算出 $C$ 个不同的 $M$ 值，并算出其平均数 $\overline M$ ，然后输出 $\big(\overline M\big)^{-1}-1$ 。

实验发现取 $C\approx 80$ 即可满足要求。严格证明十分繁琐，在此略去。

最后，怎么求子矩阵最小值？用二维 S-T 表即可，预处理 $O(nm\log n\log m)$ ，回答询问 $O(1)$ 。

## 随机化在算法中的其他应用

随机化的其他作用还包括：

- 防止被造数据者用针对性数据卡掉。例如在搜索时随机打乱邻居的顺序。
- 保证算法过程中进行的“操作”具有（某种意义上的）均匀性。例如 [模拟退火](/misc/simulated-annealing/) 算法。

在这些场景下，随机化常常（但并不总是）与乱搞、骗分等做法挂钩。

### 例： [「TJOI2015」线性代数](https://loj.ac/problem/2100)

本题的标准算法是网络流，但这里我们采取这样的乱搞做法：

- 每次随机一个位置，把这个位置取反，判断大小并更新答案。

### "代码"
```cpp
		#include <algorithm>
		#include <cstdlib>
		#include <iostream>
		
		int n;
		
		int a[510], b[510], c[510][510], d[510];
		int p[510], q[510];
		
		int maxans = 0;
		
		void check() {
			memset(d, 0, sizeof d);
			int nowans = 0;
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= n; j++) d[i] += a[j] * c[i][j];
			for (int i = 1; i <= n; i++) nowans += (d[i] - b[i]) * a[i];
			maxans = std::max(maxans, nowans);
		}
		
		int main() {
			srand(19260817);
			std::cin >> n;
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= n; j++) std::cin >> c[i][j];
			for (int i = 1; i <= n; i++) std::cin >> b[i];
			for (int i = 1; i <= n; i++) a[i] = 1;
			check();
			for (int T = 1000; T; T--) {
				int tmp = rand() % n + 1;
				a[tmp] ^= 1;
				check();
			}
			std::cout << maxans << '\n';
		}
```

### 例：(\*）随机堆

可并堆最常用的写法应该是左偏树了，通过维护树高让树左偏来保证合并的复杂度。然而维护树高有点麻烦，我们希望尽量避开。

那么可以考虑使用随机堆，即不按照树高来交换儿子，而是随机交换。

###+ note "代码"
```cpp
		struct Node {
			int child[2];
			long long val;
		} nd[100010];
		int root[100010];
		
		int merge(int u, int v) {
			if (!(u && v)) return u | v;
			int x = rand() & 1, p = nd[u].val > nd[v].val ? u : v;
			nd[p].child[x] = merge(nd[p].child[x], u + v - p);
			return p;
		}
		
		void pop(int &now) { now = merge(nd[now].child[0], nd[now].child[1]); }
```

随机堆对堆的形态没有任何硬性或软性的要求，合并操作的期望复杂度对任何两个堆（作为 `merge` 函数的参数）都成立。下证。

###+ note "期望复杂度的证明"
> 将证，对于任意的堆 $A$ ，从根节点开始每次随机选左或者右走下去（直到无路可走），路径长度（即路径上的结点数）的期望值 $h(A)\leq\log_2 (|A|+1)$ 。
> 
> - 注意到在前述过程中合并堆 $A,B$ 的期望复杂度是 $O\big(h(A)+h(B)\big)$ 的，所以上述结论可以保证随机堆的期望复杂度。
> 
> 证明采用数学归纳。边界情况是 $A$ 为空图，此时显然。下设 $A$ 非空。
> 
> 假设 $A$ 的两个子树分别为 $L,R$ ，则：
> 
> $$
> \begin{align} h(A)
> &=1+\frac{h(L)+h(R)}2
> \\\\&\leq1+\frac{\log_2(|L|+1)+\log_2(|R|+1)}2
> \\\\&=\log_2{2\sqrt{(|L|+1)(|R|+1)}}
> \\\\&\leq\log_2{\frac{2\big((|L|+1)+(|R|+1)\big)}2}
> \\\\&=\log_2{(|A|+1)} \end{align}
> $$
> 
> 证毕。

## 与随机性有关的证明技巧

以下列举几个比较有用的技巧。

自然，这寥寥几项不可能就是全部；如果你了解某种没有列出的技巧，那么欢迎补充。

### 概率上界的分析

随机算法的正确性或复杂度经常依赖于某些“坏事件”不发生或很少发生。例如，快速排序的复杂度依赖于“所选的 `pivot` 元素几乎是最小或最大元素”这一坏事件较少发生。

本节介绍几个常用于分析“坏事件”发生概率的工具。

#### 工具

**Union Bound** ：记 $A_{1\cdots m}$ 为坏事件，则

$$
\mathrm{Pr}\Big[\bigcup\limits_{i=1}^m A_i \Big]\leq \sum\limits_{i=1}^m \mathrm{Pr}[A_i]
$$

- 即：坏事件中至少一者发生的概率，不超过每一个的发生概率之和。

- 证明：回到概率的定义，把事件看成单位事件的集合，发现这个结论是显然的。

-	 这一结论还可以稍作加强：

> - 坏事件中至少一者发生的概率， **不小于** 每一个的发生概率之和，减掉每两个同时发生的概率之和。
> - 坏事件中至少一者发生的概率， **不超过** 每一个的发生概率之和，减掉每两个同时发生的概率之和，加上每三个同时发生的概率之和。
> - ……
> - 随着层数越来越多，交替出现的上界和下界也越来越紧。这一系列结论形式上类似容斥原理，证明过程也和容斥类似，这里略去。

* * *

**自然常数的使用** ： $\Big(1-\dfrac 1n\Big)^n\leq \dfrac 1e,\forall n\geq1$

- 左式关于 $n\geq 1$ 单调递增且在 $+\infty$ 处的极限是 $\dfrac 1e$ ，因此有这个结论。

- 这告诉我们，如果 $n$ 个互相独立的坏事件，每个的发生概率为 $1-\dfrac 1n$ ，则它们全部发生的概率至多为 $\dfrac 1e$ 。

* * *

**(\*) Hoeffding** 不等式：若 $X_{1\cdots n}$ 为互相独立的实随机变量且 $X_i\in [a_i,b_i]$ ，记随机变量 $X:=\sum\limits_{i=1}^n X_i$ ，则

$$
\mathrm{Pr}\Big[\big|X-\mathrm{E}[X]\big|\geq t\Big]\leq2\exp {-\dfrac {t^2}{\sum\limits_{i=1}^n (b_i-a_i)^2}}
$$

- 这一不等式限制了随机变量偏离其期望值的程度。从经验上讲，如果 $\mathrm{E}[X]$ 不太接近 $a_1+\cdots+a_n$ ，则该不等式给出的界往往相对比较紧；如果非常接近的话（例如在 [UOJ #72 全新做法](https://matthew99.blog.uoj.ac/blog/5511) 中），给出的界则往往很松，此时更好的选择是使用 (\*) [Chernoff Bound](https://en.wikipedia.org/wiki/Chernoff_bound) ，它和 Hoeffding 不等式同属于 (\*) [Concentration Inequality](https://en.wikipedia.org/wiki/Concentration_inequality) 。

#### 例子

###+ note "例：抽奖问题"
> 一个箱子里有 $n$ 个球，其中恰有 $k$ 个球对应着大奖。你要进行若干次独立、等概率的随机抽取，每次抽完之后会把球放回箱子。请问抽多少次能保证以至少 $1-\epsilon$ 的概率，满足 **每一个** 奖球都被抽到至少一次？给出一个上界即可，不要求精确答案。

与该问题类似的模型经常出现在随机算法的复杂度分析中。

###+ note "解答"
> 假如只有一个奖球，则抽取 $M:=-n\log\epsilon$ 次即可保证，因为 $M$ 次全不中的概率 $\Big(1-\dfrac 1n\Big)^{n\cdot (-\log\epsilon)}\leq e^{\log\epsilon}=\epsilon$ 。
> 
> 现在有 $k>1$ 个奖球，那么根据 Union Bound，我们只需保证每个奖球被漏掉的概率都不超过 $\dfrac \epsilon k$ 即可。于是答案是 $-n\log\dfrac \epsilon k$ 。

* * *

###+ note "例：(\*)随机选取一半元素"
> 给出一个算法，从 $n$ 个元素中等概率随机选取一个大小为 $\dfrac n2$ 的子集，保证 $n$ 是偶数。你能使用的唯一的随机源是一枚均匀硬币，同时请你尽量减少抛硬币的次数（不要求最少）。

###+ note "解法"
> 首先可以想到这样的算法：
> 
> - 通过抛 $n$ 次硬币，可以从所有子集中等概率随机选一个。
> -	 不断重复这一过程，直到选出的子集大小恰好为 $\dfrac n2$ 。
>		 - 注意到大小为 $\dfrac n2$ 的子集至少占所有子集的 $\dfrac 1n$ ，因此重复次数的期望值 $\leq n$ 。
> 
> 这一算法期望需要抛 $n^2$ 次硬币。
> 
> 另一个算法：
> 
> -	 我们可以通过抛期望 $2\lceil\log_2 n\rceil$ 次硬币来实现随机 $n$ 选 1。
>		 - 具体方法：随机生成 $\lceil\log_2 n\rceil$ 位的二进制数，如果大于等于 $n$ 则重新随机，否则选择对应编号（编号从 0 开始）的元素并结束过程。
> - 然后我们从所有元素中选一个，再从剩下的元素中再选一个，以此类推，直到选出 $\dfrac n2$ 个元素为止。
> 
> 这一算法期望需要抛 $n\lceil\log_2 n\rceil$ 次硬币。
> 
> 将两个算法缝合起来：
> 
> - 先用第一个算法随机得到一个子集。
> - 如果该子集大小不到 $\dfrac n2$ ，则利用第二个算法不断添加元素，直到将大小补到 $\dfrac n2$ 。
> - 如果该子集大小超过 $\dfrac n2$ ，则利用第二个算法不断删除元素，直到将大小削到 $\dfrac n2$ 。
> 
> 尝试分析第二、第三步所需的操作次数（即添加/删除元素的次数）：
> 
> - 记 01 随机变量 $X_i$ 表示 $i$ 是否被选入初始的子集，令 $X:=X_1+\cdots+X_n$ 表示子集大小，则第二、第三步所需的操作次数等于 $\big|X-\mathrm{E}[X]\big|$ 。在 Hoeffding 不等式中取 $t=c\cdot\sqrt n$ （其中 $c$ 为任意常数），得到 $\mathrm{Pr}\Big[\big|X-\mathrm{E}[X]\big|\geq t\Big]\leq 2e^{-c^2}$ 。也就是说，我们可以通过允许 $\Theta(\sqrt n)$ 级别的偏移，来得到任意小的常数级别的失败概率。
> 
> 至此我们已经说明：该算法可以以很大概率保证抛硬币次数在 $n+\Theta(\sqrt n\log n)$ 以内。
> 
> - 其中 $n$ 来自获得初始子集的抛硬币次数； $\Theta(\sqrt n\log n)$ 是 $\Theta(\sqrt n)$ 次添加/删除元素的总开销。
> 
> ### mdui-shadow-6 "计算期望复杂度"
>		 我们再从另一个角度分析，尝试计算该算法的期望抛硬币次数。
> 
>		 用 Hoeffding 不等式求第二、第三步中操作次数期望值的上界：
> 
>		 $$
>		 \mathrm{E}\Big[\big|X-\mathrm{E}[X]\big|\Big]=\int\limits_0^\infty \mathrm{Pr}\Big[\big|X-\mathrm{E}[X]\big|\geq t\Big]\mathrm{d}t\leq2\int\limits_0^\infty \exp {-\dfrac {t^2}n}\mathrm{d}t=\sqrt{\pi n}
>		 $$
> 
>		 从而第二、第三步所需抛硬币次数的期望值是 $\sqrt{\pi n}\cdot2\lceil\log_2 n\rceil$ 。
> 
>		 综上，该算法期望需要抛 $n+2\sqrt{\pi n}\lceil\log_2 n\rceil$ 次硬币。

### 「耦合」思想

「耦合」思想常用于同时处理超过一个有随机性的对象，或者同时处理随机的对象和确定性的对象。

#### 引子：随机图的连通性

###+ note "问题"
> 对于 $n \in \mathbf{N}^*; p,q\in [0,1]$ 且 $q\leq p$ ，求证：随机图 $G_1(n,p)$ 的连通分量个数的期望值不超过随机图 $G_2(n,q)$ 的连通分量个数的期望值。这里 $G(n,\alpha)$ 表示一张 $n$ 个结点的简单无向图 $G$ ，其中 $\dfrac {n(n-1)}2$ 条可能的边中的每一条都有 $\alpha$ 的概率出现，且这些概率互相独立。

这个结论看起来再自然不过，但严格证明却并不那么容易。

###+ note "证明思路"
> 我们假想这两张图分别使用了一个 01 随机数生成器来获知每条边存在与否，其中 $G_1$ 的生成器 $T_1$ 每次以 $p$ 的概率输出 1， $G_2$ 的生成器 $T_2$ 每次以 $q$ 的概率输出 1。这样，要构造一张图，就只需把对应的生成器运行 $\dfrac {n(n-1)}2$ 遍即可。
> 
> 现在我们把两个生成器合二为一。考虑随机数生成器 $T$ ，每次以 $q$ 的概率输出 0，以 $p-q$ 的概率输出 1，以 $1-p$ 的概率输出 2。如果我们将这个 $T$ 运行 $\dfrac {n(n-1)}2$ 遍，就能同时构造出 $G_1$ 和 $G_2$ 。具体地说，如果输出是 0，则认为 $G_1$ 和 $G_2$ 中都没有当前考虑的边；如果输出是 1，则认为只有 $G_1$ 中有当前考虑的边；如果输出是 2，则认为 $G_1$ 和 $G_2$ 中都有当前考虑的边。
> 
> 容易验证，这样生成的 $G_1$ 和 $G_2$ 符合其定义，而且在每个实例中， $G_2$ 的边集都是 $G_1$ 边集的子集。因此在每个实例中， $G_2$ 的连通分量个数都不小于 $G_1$ 的连通分量个数；那么期望值自然也满足同样的大小关系。

这一段证明中用到的思想被称为“耦合”，可以从字面意思来理解这种思想。本例中它体现为把两个本来独立的随机过程合二为一。

#### 应用： [NERC 2019 Problem G: Game Relics](https://codeforces.com/contest/1267/problem/G)

###+ note "简要题意"
> 有若干个物品，每个物品有一个价格 $c_i$ 。你想要获得所有物品，为此你可以任意地进行两种操作：
> 
> 1. 选择一个未拥有的物品 $i$ ，花 $c_i$ 块钱买下来。
> 2. 花 $x$ 块钱从所有物品（包括已经拥有的）中等概率随机抽取一个。如果尚未拥有该物品，则直接获得它；否则一无所获，但是会返还 $\dfrac x2$ 块钱。 $x$ 为输入的常数。
> 
> 问最优策略下的期望花费。

观察：如果选择抽物品，就一定会一直抽直到获得新物品为止。

- 理由：如果抽一次没有获得新物品，则新的局面和抽物品之前的局面一模一样，所以如果旧局面的最优行动是“抽一发”，则新局面的最优行动一定也是“再抽一发”。

我们可以计算出 $f_k$ 表示：如果当前已经拥有 $k$ 个不同物品，则期望要花多少钱才能抽到新物品。根据刚才的观察，我们可以直接把 $f_k$ 当作一个固定的代价，即转化为“每次花 $f_k$ 块钱随机获得一个新物品”。

###+ note "期望代价的计算"
> 显然 $f_k=\dfrac x2 \cdot (R-1)+x$ ，其中 $R$ 表示要得到新物品期望的抽取次数。
> 
> 引理：如果一枚硬币有 $p$ 的概率掷出正面，则首次掷出正面所需的期望次数为 $\dfrac 1p$ 。
> 
> - 感性理解： $\dfrac 1p \cdot p = 1$ ，所以扔这么多次期望得到 1 次正面，看起来就比较对。
> - 这种感性理解可以通过 [大数定律](https://en.wikipedia.org/wiki/Law_of_large_numbers) 严谨化，即考虑 $n\to \infty$ 次“不断抛硬币直到得到正面”的实验。推导细节略。
> - 另一种可行的证法是，直接把期望的定义带进去暴算。推导细节略。
> 
> 显然抽一次得到新物品的概率是 $\dfrac {n-k}n$ ，那么 $R=\dfrac n{n-k}$ 。

结论：最优策略一定是先抽若干次，再买掉所有没抽到的物品。

这个结论符合直觉，因为 $f_k$ 是关于 $k$ 递增的，早抽似乎确实比晚抽看起来好一点。

###+ note "证明"
> 先考虑证明一个特殊情况。将证：
> 
> - 随机过程 $A$ ：先买物品 $x$ ，然后不断抽直到得到所有物品
> - ……一定不优于……
> - 随机过程 $B$ ：不断抽直到得到 $x$ 以外的所有物品，然后如果还没有 $x$ 则买下来
> 
> 考虑让随机过程 $A$ 和随机过程 $B$ 使用同一个随机数生成器。即， $A$ 的第一次抽取和 $B$ 的第一次抽取会抽到同一个元素，第二次、第三次……也是一样。
> 
> 显然，此时 $A$ 和 $B$ 抽取的次数必定相等。对于一个被 $A$ 抽到的物品 $y\neq x$ ，观察到：
> 
> -	$A$ 中抽到 $y$ 时已经持有的物品数，一定大于等于 $B$ 中抽到 $y$ 时已经持有的物品数。
> 
> 因此 $B$ 的单次抽取代价不高于 $A$ 的单次抽取代价，进而抽取的总代价也不高于 $A$ 。
> 
> 显然 $B$ 的购买代价同样不高于 $A$ 。综上， $B$ 一定不劣于 $A$ 。
> 
> 然后可以通过数学归纳把这一结论推广到一般情况。具体地说，每次我们找到当前策略中的最后一次购买，然后根据上述结论，把这一次购买移到最后一定不劣。细节略。

基于这个结论，我们再次等价地转化问题：把“选一个物品并支付对应价格购买”的操作，改成“随机选一个未拥有的物品并支付对应价格购买”。等价性的理由是，既然购买只是用来扫尾的，那选到哪个都无所谓。

现在我们发现，“抽取”和“购买”，实质上已经变成了相同的操作，区别仅在于付出的价格不同。选择购买还是抽取，对于获得物品的顺序毫无影响，而且每种获得物品的顺序都是等可能的。

观察：在某一时刻，我们应当选择买，当且仅当下一次抽取的代价（由已经抽到的物品数确定）大于剩余物品的平均价格（等于的话则任意）。

- 可以证明，随着时间的推移，抽取代价的增速一定不低于剩余物品均价的增速。这说明从抽到买的“临界点”只有一个，进一步验证了先前结论。

最后，我们枚举所有可能的局面（即已经拥有的元素集合），算出这种局面出现的概率（已有元素的排列方案数除以总方案数），乘上当前局面最优决策的代价（由拥有元素个数和剩余物品总价确定），再加起来即可。这个过程可以用背包式的 DP 优化，即可通过本题。

* * *

**回顾** ：可以看到，耦合的技巧在本题中使用了两次。第一次是在证明过程中，令两个随机过程使用同一个随机源；第二次是把购买转化成随机购买（即引入随机源），从而使得购买和抽取这两种操作实质上“耦合”为同一种操作（即令抽取和购买操作共享一个随机源）。

## 参考资料

[^ref1]:	[PANIC - Editorial](https://discuss.codechef.com/t/panic-editorial/80145)

[^ref2]:	[UOJ NOI Round #4 Day2 题解](https://peehs-moorhsum.blog.uoj.ac/blog/6375)

[^ref3]:	[Anna Gambin and Adam Malinowski, Randomized Meldable Priority Queues](https://www.researchgate.net/publication/2801527_Randomized_Meldable_Priority_Queues)

WIKIOI

随机化技巧 - 杂项