MENU

Liuxizai's Blog

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

NOIP 2024 游记

开 T1,感觉随便贪就对了?简单证明了一下,每次考虑第一个被 ban 掉的点之前的贡献,看起来确实是对的。首先照着这个证明的思路写了一个类似双指针的东西,实现起来有点繁琐,写了一半弃了,最后按照最开始的思路写了一个逐位贪心,半个小时的时候过了大样例。

Read More

Irwin-Hall Distribution

$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 引理

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