$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(\genfrac{}{}{0ex}{}{n}{k})(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