$n$ 个在 $[0,1)$ 上均匀分布的随机变量 $\{x_i\}$，考虑它们的和 $s=\sum x_i$，则 $s$ 服从 Irwin-Hall Distribution，其累计分布函数
$$
F_s(x)=\frac 1 {n!}\sum_{k=0}^{\lfloor x\rfloor}(-1)^k\binom nk(x-k)^n.
$$
考虑单个变量的概率密度函数 $f(x)=[0\le x< 1]$，则 $F$ 是 $n$ 个 $f$ 的卷积。

Read More

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

无向图欧拉回路计数是 NPC 的。有向图欧拉回路计数则可使用 BEST 定理求解。

Read More

人生中的第一个 NOI。

Read More

邮局 是决策单调性优化 dp 的经典应用，其属于限制段数的序列划分问题，可以通过二分队列 + wqs 二分的方式做到 $O(n\log L\log n)$，其中 $L$ 指的是坐标的值域，此处不多赘述。

Read More