Schwartz-Zippel Lemma

Schwartz-Zippel Lemma

假如 $f$ 是定义在域 $F$ 上的 $n$ 元 $d$ 次非零多项式，取 $F$ 的有限子集 $S$，且 $r_1,r_2,\cdots,r_n$ 在 $S$ 内等概率选取，则 $\Pr[f(r_1,r_2,\cdots,r_n)=0]\le \dfrac{d}{|S|}$。

一个比较经典的运用是判定二分图有没有完美匹配，令 $A_{u,v}=[\text{have edge }u\rightarrow v]r_{i,j}$，其中 $r$ 是取值完全随机的 $n\times n$ 的矩阵，可以用 $\det A\not=0$ 判定，用上面式子分析一下概率还是很高的，实在不行做两次。

小练习

QOJ10514 疲配

如果没有修改操作，令 $f_S$ 表示只保留颜色集合为 $S$ 的边的条件下，$\det A$ 的值。反演一下或者暴力 $\mathcal O(3^n)$ 做就可以得到集合恰好为 $S$ 的值。加上修改也是很经典的，如果一条边 $(u,v,c)$ 颜色改成了 $c±1\in S$，$A_{u,v}$ 加一个 $r^{+/-}_{ij}x$ 的项（其中 $r^+_{i,j},r^-_{i,j}$ 也是在 $\mathbb Z_p$ 内随机取值），在 $\bmod x^2$ 意义下做就是对的，相信大家做过 [省选联考 2020 A 卷] 作业题 都会这个。

[PA 2021] Fiolki 2

见博客「2025 北京 - 2.10 花木遗址」。