$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

Description

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

Read More

偏导数

偏导数用于描述一个多元函数在某个维度的变化率。

Read More

Description

给定长度为 $n$ 的序列，$q$ 次操作，操作有两种：

• 区间加减；
• 查询某个位置上的数在多少个历史版本中 $\ge k$。

$2\le n,q\le 10^5$

Read More

Erdos-Ginzburg-Ziv Theorem

对任意 $2n-1$ 个整数，可以从中选出 $n$ 个使得这 $n$ 个数的和是 $n$ 的倍数。

形式化的，对任意 $a_1,\dots,a_{2n-1}\in \mathbb Z$，存在两两不同的 $i_1,\dots,i_n$ 使得：
$$
a_{i_1}+\dots+ a_{i_n}\equiv 0\pmod n
$$

Read More