2020-2021:teams:intrepidsword:zhongzihao:conclusion
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:intrepidsword:zhongzihao:conclusion [2020/06/11 19:58] toxel [最大反链] 完善描述 |
2020-2021:teams:intrepidsword:zhongzihao:conclusion [2021/03/26 11:41] (当前版本) toxel Irwin–Hall distribution |
||
|---|---|---|---|
| 行 22: | 行 22: | ||
| nim积还具有如下的性质： | nim积还具有如下的性质： | ||
| + | * $0\otimes x=x\otimes0=0$，$x\otimes y=0$ 当且仅当 $x=0\lor y=0$ | ||
| + | * $1\otimes x=x\otimes1=x$ | ||
| * 对全体自然数 $n$，$[0,2^{2^{n}}-1]$ 中的自然数在 nim 和和 nim 积下成一域 | * 对全体自然数 $n$，$[0,2^{2^{n}}-1]$ 中的自然数在 nim 和和 nim 积下成一域 | ||
| * 对全体自然数 $n$，$2^{2^{n}}\otimes x=2^{2^{n}}\times x(0\le x<2^{2^{n}})$ | * 对全体自然数 $n$，$2^{2^{n}}\otimes x=2^{2^{n}}\times x(0\le x<2^{2^{n}})$ | ||
| 行 101: | 行 103: | ||
| ===== KKT 条件 ===== | ===== KKT 条件 ===== | ||
| - | 设有函数 $f(\mathbf{p})$，我们要求在 $g_{1}(\mathbf{p})\le0,\cdots,g_{n}(\mathbf{p})\le0,h_{1}(\mathbf{p})=\cdots=h_{m}(\mathbf{p})=0$ 的条件下求其极值，则必要条件为： | + | 设有函数 $f(\mathbf{p})$，我们要求在 $g_{1}(\mathbf{p})\le0,\cdots,g_{n}(\mathbf{p})\le0,h_{1}(\mathbf{p})=\cdots=h_{m}(\mathbf{p})=0$ 的条件下求其极小值，则必要条件为： |
| $$ | $$ | ||
| 行 120: | 行 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意义下的组合数 ===== | ||
| 行 283: | 行 289: | ||
| 设 $f:\{1,2,\cdots,n\}\to\{1,2,\cdots,n\}$，且 $\overbrace{f\circ\cdots\circ f}^{k个}(i)=f(i)$ 对 $\{1,2,\cdots,n\}$ 成立，那么满足条件的 $f$ 指数型生成函数为 $\exp(\sum_{i\mid k-1}(x\cdot \exp(x))^{i}/i)$ | 设 $f:\{1,2,\cdots,n\}\to\{1,2,\cdots,n\}$，且 $\overbrace{f\circ\cdots\circ f}^{k个}(i)=f(i)$ 对 $\{1,2,\cdots,n\}$ 成立，那么满足条件的 $f$ 指数型生成函数为 $\exp(\sum_{i\mid k-1}(x\cdot \exp(x))^{i}/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!}$。 | ||
| ===== 其它 ===== | ===== 其它 ===== | ||
| 行 385: | 行 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|证明]] | ||
| 行 436: | 行 469: | ||
| 三角形的垂心、外心、重心和九点圆圆心共线，其中九点圆圆心到垂心和外心的距离相等，而且重心到外心的距离是重心到垂心距离的一半。 | 三角形的垂心、外心、重心和九点圆圆心共线，其中九点圆圆心到垂心和外心的距离相等，而且重心到外心的距离是重心到垂心距离的一半。 | ||
| + | ====== 图论 ====== | ||
| + | |||
| + | ===== 其它 ===== | ||
| + | |||
| + | 一个森林内部节点的度数平方和等于 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}$ | ||
| ====== 其它 ====== | ====== 其它 ====== | ||
| 行 480: | 行 529: | ||
| ===== 最大反链 ===== | ===== 最大反链 ===== | ||
| - | 给定一个非负整数数列 $\{t_{i}\}$，定义偏序集 $S=\prod_{i=1}^{n}\{x|0\le x\le t_{i},x\in\mathbb{Z}\}$，其中 $\vec{x}\preceq\vec{y}$ 当且仅当 $\forall 1\le i\le n,x_{i}\le y_{i}$。那么 $S$ 的最大反链的大小等于关于 $x_{i}$ 的不定方程 $\displaystyle{\sum_{i=1}^{n}x_{i}=\lfloor\frac{\sum_{i=1}^{n}t_{i}}{2}\rfloor}$ 的非负整数解的个数。 | + | 给定一个非负整数数列 $\{t_{i}\}$，定义偏序集 $S=\prod_{i=1}^{n}\{x|0\le x\le t_{i},x\in\mathbb{Z}\}$，其中 $\vec{x}\preceq\vec{y}$ 当且仅当 $\forall 1\le i\le n,x_{i}\le y_{i}$。那么 $S$ 的最大反链的大小等于关于 $x_{i}$ 的不定方程 $\displaystyle{\sum_{i=1}^{n}x_{i}=\lfloor\frac{\sum_{i=1}^{n}t_{i}}{2}\rfloor}$ 满足 $\forall 1\le i\le n, 0\le x_{i}\le t_{i}$ 的整数解的个数。[[some_antichain|证明]] |
| ===== 矩阵乘法 ===== | ===== 矩阵乘法 ===== | ||
2020-2021/teams/intrepidsword/zhongzihao/conclusion.1591876707.txt.gz · 最后更改: 2020/06/11 19:58 由 toxel
