Schwartz–Zippel 引理
Schwartz–Zippel 引理指出,如果我们有非零 $n$ 元 $d$ 次多项式 $p(x_1,\dots,x_n)$,对每个 $x_i$ 在有限集合 $S\subset \mathbb R$ 内独立均匀随机赋值,则
$$
\mathbb P[p(x_1,\dots,x_n)=0]\le \frac d{|S|}.
$$
证明考虑对 $n$ 进行归纳。
Schwartz–Zippel 引理指出,如果我们有非零 $n$ 元 $d$ 次多项式 $p(x_1,\dots,x_n)$,对每个 $x_i$ 在有限集合 $S\subset \mathbb R$ 内独立均匀随机赋值,则
$$
\mathbb P[p(x_1,\dots,x_n)=0]\le \frac d{|S|}.
$$
证明考虑对 $n$ 进行归纳。
无向图欧拉回路计数是 NPC 的。有向图欧拉回路计数则可使用 BEST 定理求解。