2020-2021:teams:intrepidsword:zhongzihao:conclusion
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:intrepidsword:zhongzihao:conclusion [2021/01/24 15:05] toxel add |
2020-2021:teams:intrepidsword:zhongzihao:conclusion [2021/03/26 11:41] (当前版本) toxel Irwin–Hall distribution |
||
|---|---|---|---|
| 行 122: | 行 122: | ||
| 设 $p(n)$ 为将 $n$ 写成若干个正整数和的方案数，若 $i$ 为自然数，称 $\frac{3i^{2}-i}{2}$ 和 $\frac{3i^{2}+i}{2}$ 为广义五边形数，并定义 $f(\frac{3i^{2}-i}{2}) = f(\frac{3i^{2}+i}{2}) = i$，则 $p(n) = \sum_{u,1 \le u \le n}(-1)^{f(u) - 1}p(n-u)$，其中 $u$ 为广义五边形数。$\displaystyle{\phi(x)=\prod_{i=1}^{\infty}(1-x^{i})}$ 称为欧拉函数，它是划分数生成函数的逆。$\phi(x) = \sum_{u}(-1)^{f(u)}x^{u}$，其中 $u$ 为广义五边形数。从 $0$ 开始，$p(n)$ 的前若干项为 $1,1,2,3,5,7,11,15,22,30,42,56,77$ 。 | 设 $p(n)$ 为将 $n$ 写成若干个正整数和的方案数，若 $i$ 为自然数，称 $\frac{3i^{2}-i}{2}$ 和 $\frac{3i^{2}+i}{2}$ 为广义五边形数，并定义 $f(\frac{3i^{2}-i}{2}) = f(\frac{3i^{2}+i}{2}) = i$，则 $p(n) = \sum_{u,1 \le u \le n}(-1)^{f(u) - 1}p(n-u)$，其中 $u$ 为广义五边形数。$\displaystyle{\phi(x)=\prod_{i=1}^{\infty}(1-x^{i})}$ 称为欧拉函数，它是划分数生成函数的逆。$\phi(x) = \sum_{u}(-1)^{f(u)}x^{u}$，其中 $u$ 为广义五边形数。从 $0$ 开始，$p(n)$ 的前若干项为 $1,1,2,3,5,7,11,15,22,30,42,56,77$ 。 | ||
| + | |||
| + | ===== 划分容斥 ===== | ||
| + | |||
| + | 在集合 $S$ 上定义一个等价关系，有 $n$ 个位置可以取 $S$ 中的值，要求两两值不同，另外还有一些别的限制。设 $M=\{1,2,\cdots,n\}$，可以在 $M$ 的划分上进行容斥，$P$ 表示 $P$ 中每个子集中的元素相等，而子集间的关系不受限制，那么 $P$ 的容斥系数是 $\prod_{Q\in P}(-1)^{|Q|-1}(|Q|-1)!$。特别地，如果这 $n$ 的位置本质相同，还可以枚举划分数来做。[[project_euler#writing_n_as_the_product_of_k_distinct_positive_integers|证明]] | ||
| ===== 模2意义下的组合数 ===== | ===== 模2意义下的组合数 ===== | ||
| 行 287: | 行 291: | ||
| ===== 随机串包含给定串的期望长度 ===== | ===== 随机串包含给定串的期望长度 ===== | ||
| - | 设有一串 $S$，从一个空串开始，每次等概率随机往后面加一个字符，包含 $S$ 时停止。期望长度为 $\sum_{i=1}^{|S|}[1..i\text{ is border}]|\Sigma|^{i}$。 | + | 设有一串 $S$，从一个空串开始，每次等概率随机往后面加一个字符，包含 $S$ 时停止。期望长度为 $\sum_{i=1}^{|S|}[1..i\text{ is border}]|\Sigma|^{i}$。[[random_string|证明]] |
| + | ===== 二项式反演 ===== | ||
| + | |||
| + | $$ | ||
| + | f_{n}=\sum_{i=0}^{n}(-1)^{i}{n\choose i}g_{i}\Leftrightarrow g_{n}=\sum_{i=0}^{n}(-1)^{i}{n\choose i}f_{i}\\ | ||
| + | f_{n}=\sum_{i=0}^{n}{n\choose i}g_{i}\Leftrightarrow g_{n}=\sum_{i=0}^{n}(-1)^{n-i}{n\choose i}f_{i} | ||
| + | $$ | ||
| + | |||
| + | ===== 广义二项式定理 ===== | ||
| + | |||
| + | $(x+y)^{\alpha}=\sum_{k=0}^{+\infty}{\alpha\choose k}x^{\alpha-k}y^{k}$，其中 ${\alpha\choose k}=\frac{\alpha(\alpha-1)\cdots(\alpha-k+1)}{k!}=\frac{(\alpha)_{k}}{k!}$。 | ||
| ===== 其它 ===== | ===== 其它 ===== | ||
| 行 391: | 行 405: | ||
| [[similar_euclid|证明]] | [[similar_euclid|证明]] | ||
| + | |||
| + | ===== 莫比乌斯反演 ===== | ||
| + | |||
| + | $$ | ||
| + | f_{n}=\sum_{d\mid n}g_{d}\Leftrightarrow g_{n}=\sum_{d\mid n}\mu(\frac{n}{d})f_{d}\\ | ||
| + | f_{n}=\sum_{n\mid d}g_{d}\Leftrightarrow g_{n}=\sum_{n\mid d}\mu(\frac{d}{n})f_{d} | ||
| + | $$ | ||
| + | |||
| + | 若 $t$ 为完全积性函数，且 $t(1)=1$，那么 | ||
| + | |||
| + | $$ | ||
| + | f_{n}=\sum_{i=1}^{n}t(i)g_{\lfloor\frac{n}{i}\rfloor}\Leftrightarrow g_{n}=\sum_{i=1}^{n}\mu(i)t(i)f_{\lfloor\frac{n}{i}\rfloor} | ||
| + | $$ | ||
| ===== 其他 ===== | ===== 其他 ===== | ||
| - | $x^{2}+y^{2}=t$ 的整数解的个数为 $4(\sigma_{1}(t)-\sigma_{3}(t))$，其中 $\sigma_{1}(t)$ 表示 $t$ 的约数中模 $4$ 余 $1$ 的个数，$\sigma_{3}(t)$ 表示 $t$ 的约数中模 $4$ 余 $3$ 的个数。 | + | $x^{2}+y^{2}=t$ 的整数解的个数为 $4(\sigma_{1}(t)-\sigma_{3}(t))$，其中 $\sigma_{1}(t)$ 表示 $t$ 的约数中模 $4$ 余 $1$ 的个数，$\sigma_{3}(t)$ 表示 $t$ 的约数中模 $4$ 余 $3$ 的个数。这一结论等价于，若 $t$ 中某 $4k+3$ 型的质数 $p$ 有奇数个，则无解。否则，答案为所有 $4k+1$ 型质数的积的约数个数乘 $4$。 |
| 设有 $m$ 个正整数 $c_{1},c_{2},\cdots,c_{m}$，且严格递增。所有大于等于 $c_{m-1}c_{m}$，且能被 $\gcd(c_{1},c_{2},\cdots,c_{m})$ 整除的整数可以用这 $m$ 个数使用非负整系数线性表示。[[http://clatisus.com/The%202016%20ACM-ICPC%20Asia%20China-Final%20(Shanghai)%20Contest#i.-cherry-pick|证明]] | 设有 $m$ 个正整数 $c_{1},c_{2},\cdots,c_{m}$，且严格递增。所有大于等于 $c_{m-1}c_{m}$，且能被 $\gcd(c_{1},c_{2},\cdots,c_{m})$ 整除的整数可以用这 $m$ 个数使用非负整系数线性表示。[[http://clatisus.com/The%202016%20ACM-ICPC%20Asia%20China-Final%20(Shanghai)%20Contest#i.-cherry-pick|证明]] | ||
| 行 447: | 行 474: | ||
| 一个森林内部节点的度数平方和等于 2*(长度为 2 的路径数+长度为 3 的路径数)。 | 一个森林内部节点的度数平方和等于 2*(长度为 2 的路径数+长度为 3 的路径数)。 | ||
| + | |||
| + | 一个 $n\times m$ 的四连通网格图的生成树数量为 $\prod_{i=1}^{m-1}\prod_{j=1}^{n-1}(4\sin^2(\pi i/2m)+4\sin^2(\pi j/2n))$ | ||
| + | ====== 概率论 ====== | ||
| + | |||
| + | ===== 一维随机游走 ===== | ||
| + | |||
| + | 在 $[0,n]$ 上随机游走，从 $x$ 出发，每次等概率移动 $\pm 1$，走到 $0$ 的期望步数是 $x(2n-x)$。 | ||
| + | |||
| + | ===== Irwin–Hall distribution ===== | ||
| + | |||
| + | 设有 $n$ 个独立同分布的变量 $X_{i}\sim U[0,1]$，那么 $\sum_{i=1}^{n}X_{i}$ 的累积分布函数是 $\frac{1}{n!}\sum_{k=0}^{\lfloor x\rfloor}(-1)^{k}{n\choose k}(x-k)^{n}$，概率密度函数是 $\frac{1}{(n-1)!}\sum_{k=0}^{\lfloor x\rfloor}(-1)^{k}{n\choose k}(x-k)^{n-1}$ | ||
| ====== 其它 ====== | ====== 其它 ====== | ||
2020-2021/teams/intrepidsword/zhongzihao/conclusion.1611471943.txt.gz · 最后更改: 2021/01/24 15:05 由 toxel
