MENU

Liuxizai's Blog

我们的心就像那天空一样 永不分离

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$ 进行归纳。

Read More

做题笔记 2024 NFLS NOI 模拟赛

2024.5.21

树数术

给一颗 $n$ 个点的树和一个长为 $m$ 的序列 $a_{1\dots m}$,序列中每个数表示树上的一个节点。$q$ 次询问,每次询问给出 $a$ 的 $k$ 个子区间,将这 $k$ 个子区间顺次拼接成新的序列,求新序列上有多少个数是前缀 $\operatorname{lca}$。

Read More