$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

Description

有 $m$ 个篮子放在一个环上，篮子按顺时针顺序编号为 $1\sim m$。有 $n$ 个球，第 $i$ 个球放在篮子 $a_i$ 中，$a_i$ 互不相同。接下来反复进行如下操作：从 $1\sim n$ 中等概率选出一个数 $i$，若球 $i$ 已被扔掉则什么都不做；否则将球 $i$ 移动到顺时针方向的下一个篮子里，如果下一个篮子里本来有一个球 $j$，则将球 $j$ 扔掉。进行一次上述操作总是花费 $1$ 单位时间，所有篮子中只剩下一个球时结束此过程。求过程持续的期望时间，答案对 $10^9 + 7$ 取模。

$1\le n\le 3\times 10^5, n\le m\le 10^9$

Read More

约定：题目标题后会用一个 0.0 到 1.0 间的实数表示本题有多少部分由自己解决。0.0 表示完全根据题解完成，1.0 表示完全由自己完成，其余实数则表示部分参考题解。

Read More

Description

给定 $n,p,k$，对于每个 $r\in[0,k]$，求出 $\mathbb{F}_p$ 上有多少个秩为 $r$ 的 $n\times n$ 矩阵。

Read More