部分链接尚未搬运~

====== 博弈论 ======

===== 威佐夫游戏 =====

有两堆石子，两人轮流取，每次可以从一堆中取若干颗石子，也可以从两堆中取一样多的石子。负态为 $\{\lfloor k\cdot\frac{1+\sqrt{5}}{2}\rfloor, k+\lfloor k\cdot\frac{1+\sqrt{5}}{2}\rfloor\}(k = 0,1,2,\cdots)$

===== 翻硬币游戏 =====

翻硬币游戏是指这样的一种组合游戏：有 $n$ 枚硬币排成一排，开始时它们有的正面朝上，有的反面朝上，两名玩家轮流按照一定的规则，翻转一些硬币，最后不能操作者输。这里的规则必须满足以下两点：

  * 最右边的硬币必须是从正面翻转到反面（为了保证游戏结束）
  * 规则允许的翻转位置集合唯一取决于最右侧硬币的位置，而与之前的操作、玩家等无关（为保证这是一个平等博弈）

翻硬币游戏有这样一个结论：一个局面的 $sg$ 值等于所有正面硬币的 $sg$ 值的异或，以 ''%%H%%'' 表示正，''%%T%%'' 表示反，例如：$sg(THHTTH)=sg(TH)\oplus sg(TTH)\oplus sg(TTTTTH)$。

===== Nim 积 =====

$a\otimes b=\text{mex}\{a'\otimes b\oplus a\otimes b'\oplus a'\otimes b'|0\le a'<a,0\le b'<b\}$ 满足交换律，结合律，对 nim 和（异或）满足分配律。全体非负整数在 nim 和和 nim 积下成一域。Tartan Games（即二维硬币游戏）的 $sg$ 值是对应行列的 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$，$2^{2^{n}}\otimes x=2^{2^{n}}\times x(0\le x<2^{2^{n}})$
  * 对全体自然数 $n$，$2^{2^{n}}\otimes 2^{2^{n}}=\frac{3}{2}\cdot2^{2^{n}}=2^{2^{n}}\oplus2^{2^{n}-1}$

===== surreal number =====

$surreal\;number$ 是一个包含无穷小、无穷大和实数的域，用它可以十分方便地研究一些不平等博弈问题。$surreal\;number$ 定义为一个集合对 $\{L|R\}$，其中 $L$ 中的每个元素小于 $R$ 中的每个元素。我们称 $x\le y$ 当且仅当不存在 $x_{L}\in X_{L}$ 使得 $y\le x_{L}$，且不存在 $y_{R}\in Y_{R}$ 使得 $y_{R}\le x$。 $surreal\;number$ 有如下的一些性质：

  * 对于一个 $surreal\;number$ $x=\{L|R\}$ ，$x$ 大于 $L$ 中的任意一个元素，小于 $R$ 中的任意一个元素。
  * 对于一个 $surreal\;number$ $x=\{L|R\}$ ，若 $L$ 有最大值 $l_{max}$，则 $x=\{l_{max}|R\}$，对于 $R$ 同理。
  * 设 $a$ 到 $b$ 之间最早出生的 $surreal\;number$ 在第 $i$ 天出生，那么在 $a$ 到 $b$ 之间且在第 $i$ 天出生的 $surreal\;number$ 有且只有一个。
  * 若 $a<x<b$ 且 $x$ 是 $a$ 和 $b$ 之间最早出生的 $surreal\;number$，则 $x=\{a|b\}$

$surreal\;number$ 的加法法则为 $x+y=\{X_{L}|X_{R}\}+\{Y_{L}|Y_{R}\}=\{X_{L}+y,x+Y_{L}|X_{R}+y,x+Y_{R}\}$

$surreal\;number$ 的取反法则为 $-x=-\{X_{L}|X_{R}\}=\{-X_{R}|-X_{L}\}$

$surreal\;number$ 的乘法法则为 $xy=\{X_{L}|X_{R}\}\{Y_{L}|Y_{R}\}=\{X_{L}y+xY_{L}-X_{L}Y_{L}，X_{R}y+xY_{R}-X_{R}Y_{R}|X_{L}y+xY_{R}-X_{L}Y_{R}，xY_{L}+X_{R}y-X_{R}Y_{L}\}$

$surreal\;number$ 的取逆法则为 $\displaystyle{\frac{1}{y}=\{0,\frac{1+(y^{R}-y)(\frac{1}{y})^{L}}{y^{R}},\frac{1+(y^{L}-y)(\frac{1}{y})^{R}}{y^{L}}|\frac{1+(y^{L}-y)(\frac{1}{y})^{L}}{y^{L}},\frac{1+(y^{R}-y)(\frac{1}{y})^{R}}{y^{R}}\}}$，其中 $y^{L}>0,y^{R}>0$

设有一组合游戏处于局面 $P$，玩家 $L$ 可以转移到的状态为 $P^{L}$，玩家 $R$ 可以转移到的状态为 $P^{R}$，我们记 $P=\{P^{L}|P^{R}\}$。那么：

  * 若 $P>0$，则不论先手还是后手，$L$ 获胜
  * 若 $P<0$，则不论先手还是后手，$R$ 获胜
  * 若 $P=0$，则后手获胜

类似于 $Nim$ 和游戏，若有 $n$ 个不平等游戏 $P_{1},\cdots,P_{n}$，它们分别对应的 $surreal\;number$ 为 $x_{1},\cdots,x_{n}$，则 $P_{1}+\cdots+P_{n}$ 对应的 $surreal\;number$ 为 $x_{1}+\cdots+x_{n}$。

最后给出一些无穷大和无穷小的 $surreal\;number$

$$
\begin{aligned}\\
&\{0|1,\frac{1}{2},\frac{1}{4},\cdots\}=\epsilon(无穷小)\\
&\{0,1,2,3,\cdots|\}=\omega(无穷大)\\
&\{\epsilon|1,\frac{1}{2},\frac{1}{4},\cdots\}=2\epsilon\\
&\{0|\epsilon\}=\frac{\epsilon}{2}\\
&\{0,1,2,3,\cdots,\omega|\}=\omega+1\\
&\{0,1,2,3,\cdots|\omega\}=\omega-1\\
&\{\omega|\omega+1\}=\omega+\frac{1}{2}\\
\end{aligned}\\
$$

===== SJ 定理 =====

对一个 $Nim$ 游戏，如果定义使得所有子游戏的 $sg$ 值为 $0$ 的玩家胜利，先手必胜的条件为：

  * 游戏的 $sg$ 值为 $0$ 且所有子游戏 $sg$ 值均不超过 $1$。
  * 游戏的 $sg$ 值不为 $0$ 且至少一个子游戏 $sg$ 值超过 $1$。

====== 数学分析 ======

===== Wallis公式 =====

$$
\frac{\pi}{2} = \lim_{n \to +\infty}\frac{[\frac{(2n)!!}{(2n-1)!!}]^{2}}{2n+1}
$$

===== Stirling公式 =====

$$
n!\sim\sqrt{2\pi n}(\frac{n}{e})^{n}
$$

===== n维球 =====

$n$维球的体积公式：$\displaystyle{\frac{\pi^{\frac{n}{2}}}{\Gamma(\frac{n}{2}+1)}r^{n}}$

$n$维球的表面积公式：$\displaystyle{\frac{2\pi^{\frac{n}{2}}}{\Gamma(\frac{n}{2})}r^{n-1}=V_{n}'(r)}$

其中伽马函数 $\Gamma(z)=\int_{0}^{\infty}x^{z-1}e^{-x}\mathbb{d}x$ ，满足

  * $\Gamma(1)=1,\Gamma(z+1)=z\Gamma(z)(z>0)$
  * $\Gamma(1-z)\Gamma(z)=\frac{\pi}{\sin(\pi z)}(z\notin\mathbb{Z})$
  * $\Gamma(z)\Gamma(z+\frac{1}{2})=2^{1-2z}\sqrt{\pi}\Gamma(2z)$
  * $\Gamma(\frac{1}{2})=\sqrt{\pi}$

===== 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$ 的条件下求其极小值，则必要条件为：

$$
\begin{cases}
&\nabla f(\mathbf{p})+\sum_{i=1}^{m}\lambda_{i}\nabla h_{i}(\mathbf{p})+\sum_{i=1}^{n}\mu_{i}\nabla g_{i}(\mathbf{p})=0\\
&h_{i}(\mathbf{p})=0\\
&\mu_{i}g_{i}(\mathbf{p})=0\\
&\mu_{i}\ge0\\
&g_{i}(\mathbf{p})\le0
\end{cases}
$$

可以看出这是拉格朗日乘因子法的推广。如果 $f$ 是凸函数（注意凸函数要求定义域是凸集，即 $g$ 和 $h$ 的限制以及 $f$ 的定义域都要是凸集），那么 KKT 条件是充要的。

====== 组合数学 ======

===== 划分数 =====

设 $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意义下的组合数 =====

${n\choose m}\% 2=!(m\And\sim n)$。由此易知，${n\choose m}\% 2=1$，当且仅当 $n$ 在 $m$ 为 $1$ 的二进制位上也都为 $1$。易知，${n+m\choose m}\% 2=1$，当且仅当 $n$ 在 $m$ 为 $1$ 的二进制位上都为 $0$。

===== 默慈金数 =====

设 $M_{n}$ 表示在一个圆上的 $n$ 个不同点间，画出彼此不相交的弦的全部方法的总数。$M_{0} = M_{1} = 1, M_{n + 1} = M_{n}+\sum_{i=0}^{n-1}M_{i}M_{n-i-1} = \frac{2n+3}{n+3}M_{n}+\frac{3n}{n+3}M_{n-1}$。它也可以表示数列 $\{a_{i}\}(0 \le i \le n)$ 的数量，满足：$a_{0} = a_{n} = 0, a_{i} \ge 0, |a_{i}-a_{i + 1}| \le 1$。从 $0$ 开始，$M_{n}$ 的前若干项为 $$
\begin{aligned}
&1,1,2,4,9,21,51,127,323,835,2188,\\
&5798,15511,41835,113634,310572,853467,\\
&2356779,6536382,18199284,50852019,142547559,\\
&400763223,1129760415,3192727797,9043402501,\\
&25669818476,73007772802,208023278209,593742784829
\end{aligned}
$$

===== 卡特兰数 =====

设 $C_{0}=1,C_{n}=\sum_{i=0}^{n-1}C_{i}C_{n-i-1}$，它满足 $\displaystyle{C_{n} = \frac{C_{2n}^{n}}{n+1}}$，它可以表示：

  * $n$ 对括号组成的合法的表达式种数
  * $n$ 个结点不同构二叉树的方案数
  * $n \times n$ 格点中不越过对角线的单调路径的个数。单调路径是指从左下角走到右上角，每步向右或向上。
  * 通过连接顶点将 $n+2$ 条边的凸多边形分成三角形的方案数
  * 以 $\{1, 2, \cdots, n\}$ 为进栈序列的合法出栈序列个数
  * 集合 $\{1, 2, \cdots, n\}$ 的不交叉划分的个数
  * 用 $n$ 个长方形填充一个高度为 $n$ 的阶梯状图形的方法个数

从 $0$ 开始， $C_{n}$ 的前若干项为 $$
\begin{aligned}
&1,1,2,5,14,42,132,429,1430,\\
&4862,16796,58786,208012,742900,\\
&2674440,9694845,35357670,129644790,\\
&477638700,1767263190
\end{aligned}
$$

===== 伯努利数 =====

$B_{0} = 1, B_{i}=1-\sum_{j = 0}^{i-1}C_{i}^{j}\frac{B_{j}}{i-j+1}.$ 伯努利数的指数型母函数是 $\frac{x}{e^{x}-1}.$ 伯努利数可用于计算等幂和：$\sum_{k = 1}^{n}k^{m} = \frac{1}{m+1}\sum_{k=0}^{m}C_{m+1}^{k}B_{k}n^{m+1-k}.$ 从 $0$ 开始，$B_{n}$ 的前若干项为 $1,\frac{1}{2},\frac{1}{6},0,-\frac{1}{30},0,\frac{1}{42},0,-\frac{1}{30}$

===== 上升阶乘幂和下降阶乘幂 =====

$(x)^{(n)}=x(x+1)(x+2)\cdots(x+n-1)$ 称为上升阶乘幂， $(x)_{n}=x(x-1)(x-2)\cdots(x-n+1)$ 称为下降阶乘幂。 满足：

  * $(a+b)^{(n)}=\sum_{i=0}^{n}{n\choose i}(a)^{(n-j)}(b)^{(j)}$
  * $(a+b)_{n}=\sum_{i=0}^{n}{n\choose i}(a)_{n-j}(b)_{j}$
  * $(x)_{m}(x)_{n}=\sum_{k=0}^{m}{m\choose k}{n\choose k}k!(x)_{m+n-k}$

===== 斯特林数 =====

==== 第一类斯特林数 ====

$\begin{bmatrix}n\\k\end{bmatrix}$ 表示 $n$ 个元素的置换中能被分解为 $k$ 个循环的置换个数，并定义 $s(n,k)=(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}$。 $\begin{bmatrix}n+1\\k\end{bmatrix}=n\begin{bmatrix}n\\k\end{bmatrix}+\begin{bmatrix}n\\k-1\end{bmatrix}(k>0)$，$\begin{bmatrix}0\\0\end{bmatrix}=1$，$\begin{bmatrix}n\\0\end{bmatrix}=\begin{bmatrix}0\\n\end{bmatrix}=0(n>0)$。 该数列满足：

  * $(x)^{(n)}=\sum_{k=0}^{n}\begin{bmatrix}n\\k\end{bmatrix}x^{k}$
  * $(x)_{n}=\sum_{k=0}^{n}s(n,k)x^{k}$

也就是说，对于一个固定的 $n$，$(x)^{(n)}$ 和 $(x)_{n}$ 分别是 $\{\begin{bmatrix}n\\k\end{bmatrix}\}$ 和 $\{s(n,k)\}$ 的生成函数。

对于一个固定的 $k$，$\{\begin{bmatrix}n\\k\end{bmatrix}\}$ 的指数型生成函数为：$\displaystyle{\frac{\ln^{k}\frac{1}{1-x}}{k!}=\sum_{n=k}^{+\infty}\begin{bmatrix}n\\k\end{bmatrix}\frac{x^{n}}{n!}}$。

另外还有：

  * $\begin{bmatrix}n\\m\end{bmatrix}=\sum_{k}\begin{bmatrix}n+1\\k+1\end{bmatrix}{k\choose m}(-1)^{m-k}$
  * $\begin{bmatrix}n+1\\m+1\end{bmatrix}=\sum_{k=0}^{n}\begin{bmatrix}k\\m\end{bmatrix}\frac{n!}{k!}$
  * $\begin{bmatrix}m+n+1\\m\end{bmatrix}=\sum_{k=0}^{m}(n+k)\begin{bmatrix}n+k\\k\end{bmatrix}$
  * $\begin{bmatrix}n\\l+m\end{bmatrix}{l+m\choose l}=\sum_{k}\begin{bmatrix}k\\l\end{bmatrix}\begin{bmatrix}n-k\\m\end{bmatrix}{n\choose k}$

==== 第二类斯特林数 ====

$\begin{Bmatrix}n\\k\end{Bmatrix}$ 表示有 $n$ 个元素的集合划分为 $k$ 个集合的方案数。$\begin{Bmatrix}n+1\\k\end{Bmatrix}=k\begin{Bmatrix}n\\k\end{Bmatrix}+\begin{Bmatrix}n\\k-1\end{Bmatrix}(k>0)$，$\begin{Bmatrix}0\\0\end{Bmatrix}=1$，$\begin{Bmatrix}n\\0\end{Bmatrix}=\begin{Bmatrix}0\\n\end{Bmatrix}=0(n>0)$。 该数列满足：

  * $\begin{Bmatrix}n\\k\end{Bmatrix}=\frac{1}{k!}\sum_{i=0}^{k}(-1)^{i}{k\choose i}(k-i)^{n}$

容易注意到这是一个卷积形式，可以 $\mathcal{O}(n\log n)$ 地求出一个 $n$ 对应的所有第二类斯特林数

  * $\sum_{k=0}^{n}\begin{Bmatrix}n\\k\end{Bmatrix}(x)_{k}=x^{n}$
  * $B_{n}=\sum_{k=0}^{n}\begin{Bmatrix}n\\k\end{Bmatrix}$（其中 $B_{n}$ 是贝尔数）

对于一个固定的 $k$，$\{\begin{Bmatrix}n\\k\end{Bmatrix}\}$ 的生成函数为 $\displaystyle{\sum_{n=k}^{+\infty}\begin{Bmatrix}n\\k\end{Bmatrix}x^{n}=\frac{x^{k}}{\prod_{i=1}^{k}1-kx}}$，其指数型生成函数为 $\displaystyle{\sum_{n=k}^{+\infty}\begin{Bmatrix}n\\k\end{Bmatrix}\frac{x^{n}}{n!}=\frac{(e^{x}-1)^{k}}{k!}}$。

===== 贝尔数 =====

设 $B_{n}$ 表示基数为 $n$ 的集合的划分方法数，则 $B_{n}$ 满足 $B_{n+1}=\sum_{k=0}^{n}{n\choose k}B_{k}$，$B_{n}=\sum_{k=0}^{n}S(n, k)$，其中 $S$ 是第二类斯特林数，对任意质数 $p$ 有 $B_{n+p^{m}}\equiv mB_{n}+B_{n+1}\pmod{p}$，其指数型母函数是 $\sum_{n=0}^{\infty}\frac{B_{n}}{n!}x^{n}=e^{e^{x}-1}$。从 $0$ 开始，$B_{n}$ 的前若干项为 $$
\begin{aligned}
&1,1,2,5,15,52,203,877,\\
&4140,21147,115975,678570,\\
&4213597,27644437,190899322,\\
&1382958545,10480142147,82864869804,\\
&682076806159,5832742205057,51724158235372,\\
&474869816156751,4506715738447323,44152005855084346,\\
&445958869294805289,4638590332229999353,49631246523618756274
\end{aligned}
$$

===== Burnside 引理 =====

设 $G$ 是一个有限群，作用于集合 $X$ 上，对 $\forall g\in G$，$X^{g}$ 表示 $X$ 中在 $g$ 作用下的不动元素的集合，$|X/G|$ 表示 $X$ 在 $G$ 作用下的轨道数，则有 $|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^{g}|$。

===== Polya 定理 =====

设 $\bar{G}$ 是 $n$ 个对象的一个置换群，用 $m$ 种颜色涂染这 $n$ 个对象，则不同染色的方案数为 $l=\frac{1}{|\bar{G}|}(m^{c(\bar{a_{1}})}+m^{c(\bar{a_{2}})}+\cdots+m^{c(\bar{a_{g}})})$ ，其中 $c(\bar{a_{i}})$ 表示置换 $\bar{a_{i}}$ 的循环节数。

===== 切比雪夫多项式 =====

第一类切比雪夫多项式为 $T_{n}(\cos x)=\cos nx$ ，满足 $\displaystyle{[x^{m}]T_{n}=(-1)^{\frac{n-m}{2}}\frac{n}{m}{\frac{n+m}{2}-1\choose m-1}2^{m-1}}$ 。第二类切比雪夫多项式为 $U_{n}(\cos x)=\frac{\sin(n+1)x}{\sin x}$ ，满足 $\displaystyle{[x^{m}]U_{n}=(-1)^{\frac{n-m}{2}}{\frac{n+m}{2}\choose \frac{n-m}{2}}2^{m}}$ 。

===== 杨式矩阵和钩子公式 =====

杨式矩阵是指满足以下两个条件的矩阵：

  * 如果格子 $(i,j)$ 没有元素，则它右边和上边的相邻格子也一定没有元素。
  * 如果格子 $(i,j)$ 有元素 $a_{i,j}$ ，则它右边和上边的相邻格子要么没有元素，要么有元素且比 $a_{i,j}$ 大。

$1\sim n$所组成杨氏矩阵的个数可以通过下面的递推式得到：

$F_{1}=1,F_{2}=2,F_{n}=F(n-1)+(n-1)F(n-2)$

钩子公式是指：对于给定形状，不同的杨氏矩阵的个数为：$n!$ 除以每个格子的钩子长度加 $1$ 的积。其中钩子长度定义为该格子右边的格子数和它上边的格子数之和。

===== 全错排 =====

$1\sim n$ 的全错排数量为 $n!\sum_{i=0}^{n}(-1)^{i}\frac{1}{i!}$

===== 可拆分排列 =====

排列的直和是指将两个排列拼起来，将右边的排列平移；排列的斜和是指将两个排列拼起来，将左边的排列平移。例如 $1,2$ 和 $1,2,3$ 的直和为 $1,2,3,4,5$，斜和为 $4,5,1,2,3$。定义可拆分排列为可以由 $1$ 这一种排列经过若干次斜和和直和的运算得到的排列。

===== 大 Schr\ddot{o}der 数 =====

设 $S_{n}$ 表示从 $(0,0)$ 走到 $(n,n)$，每次只能向右、向上、向右上走一步，且不能跨过 $(0,0)$ 到 $(n,n)$ 的对角线的不同走法数量。那么有 $S_{0}=1,S_{1}=2,S_{n}=3S_{n-1}+\sum_{k=1}^{n-2}S_{k}S_{n-k-1}$。$S_{n}$ 的生成函数是 $\frac{1-x-\sqrt{x^{2}-6x+1}}{2x}$。$S_{n}=\sum_{i=0}^{n}\frac{1}{n-i+1}\frac{(2n-i)!}{i!((n-i)!)^{2}}$。

$S_{n}$ 还可以表示长度为 $n+1$ 的可拆分排列的数量。

从 $0$ 开始，$S_{n}$ 的前若干项为 $$
\begin{aligned}
&1,2,6,22,90,394,\\
&1806,8558,41586,206098,\\
&1037718,5293446,27297738,\\
&142078746,745387038,3937603038,\\
&20927156706,111818026018,600318853926,\\
&3236724317174,17518619320890,95149655201962,\\
&518431875418926,2832923350929742,15521467648875090
\end{aligned}
$$

===== 小 Schr\ddot{o}der 数 =====

设 $s_{0}=1,s_{i+1}=\frac{S_{i}}{2}$，那么 $s_{n}=\frac{1}{n}((6n-9)s_{n-1}-(n-3)s_{n-2})$。$s_{n}$ 可以表示：

  * 将 $n+1$ 边形剖分的方案数
  * 给 $n$ 个数加括号的方案数

===== 库默尔定理 =====

设 $p$ 为质数，$a,b$ 在 $p$ 进制下的表示分别为 $\overline{\cdots a_{n}\cdots a_{0}}$ 和 $\overline{\cdots b_{n}\cdots b_{0}}$，那么 ${a\choose b}$ 中含有质因子 $p$ 的个数为满足 $\overline{\cdots a_{i}\cdots a_{0}}<\overline{\cdots b_{i}\cdots b_{0}}$ 的下标 $i$ 的个数。特别的，当 $a<b$ 时，${a\choose b}=0$，而满足条件的 $i$ 也有无穷多个。从另一种角度来说，也可以理解成 $b$ 和 $a-b$ 在做 $p$ 进制加法时产生进位的次数。这可以得到一个显然的推论：${a\choose b}$ 中 $p$ 的个数不超过 $\log_{p}a$。

===== 不动函数的数量 =====

设 $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!}$。
===== 其它 =====

$\sum{n\choose2k}{k\choose m}=\frac{n}{n-m}{n-m\choose n-2m}2^{n-2m-1}$

====== 数论 ======

===== 连分数与佩尔方程 =====

记 $<x_{0},x_{1},x_{2},x_{3},\cdots> = x_{0}+\frac{1}{x_{1}+\frac{1}{x_{2}+\frac{1}{x_{3}+\cdots}}}$ ，其中 $x_{i}>0(i\ge1)$ 。称 $\frac{p_{n}}{q_n}=<x_{0},x_{1},\cdots,x_{n}>$ 为它的第 $n$ 个渐近分数。补充定义 $p_{-1}=1,q_{-1}=0$ ，则有递推式 $p_{n}=x_{n}p_{n-1}+p_{n-2},q_{n}=x_{n}q_{n-1}+q_{n-2}(n\ge1)$ 。对无限简单连分数，我们称 $\xi_{n}=<x_{n},x_{n+1},\cdots>$ 为它的第 $n$ 个完全商，满足 $\xi_{0}=\frac{p_{n}\xi_{n+1}+p_{n-1}}{q_{n}\xi_{n+1}+q_{n-1}}$。一个实数是二次根式当且仅当它是循环简单连分数，我们用 $<x_{0},\cdots,x_{m_{0}-1},<\overline{x_{m_{0}},\cdots,x_{m_{0}+l-1}}>>$ ，其中 $l$ 是 $\xi_{0}$ 的周期。设 $\xi_{0}=\frac{\sqrt{d}+c_{0}}{r_{0}},q_{0}|d-c^{2}_{0}$ ，我们有 $\xi_{n}=\frac{\sqrt{d}+c_{n}}{r_{n}}$ ，其中 $r_{n+1}=r_{n-1}+\frac{c_{n}^{2}-c_{n+1}^{2}}{r_{n}}=r_{n-1}+(c_{n}-c_{n+1})x_{n}$,$c_{n+1}=x_{n}r_{n}-c_{n}$,$a_{n}=\lfloor\xi_{n}\rfloor(n\ge1)$ 。

我们给出两个不定方程：$x-dy^{2}=1$ 和 $x-dy^{2}=-1$，若 $d$ 为完全平方数，则第一个方程只有解 $(\pm1,0)$，第二个方程无解。若 $d$ 不为完全平方数，设 $\xi_{0}=\sqrt{d}$，设它的循环连分数周期为 $l$，渐近分数为 $\frac{p_{n}}{q_{n}}$，则：

  * 当 $l$ 为偶数时，第一个方程的全体正解为 $x=p_{jl-1},y=q_{jl-1},j=1,2,3,\cdots$，第二个方程无解
  * 当 $l$ 为奇数时，第一个方程的全体正解为 $x=p_{jl-1},y=q_{jl-1},j=2,4,6,\cdots$，第二个方程的全体正解为 $x=p_{jl-1},y=q_{jl-1},j=1,3,5,\cdots$

还有另一种更加简单的表示方法：

  * 当 $l$ 为偶数时，第一个方程的全体解为 $x+y\sqrt{d}=\pm(p_{l-1}\pm q_{l-1}\sqrt{d})^{j},j=0,1,2,\cdots$，第二个方程无解
  * 当 $l$ 为奇数时，第一个方程的全体正解为 $x+y\sqrt{d}=\pm(p_{l-1}\pm q_{l-1}\sqrt{d})^{j},j=0,2,4,\cdots$，第二个方程的全体正解为 $x+y\sqrt{d}=\pm(p_{l-1}\pm q_{l-1}\sqrt{d})^{j},j=1,3,5,\cdots$

设有一佩尔方程 $x^{2}-ny^{2}=k$，利用 Brahmagupta’s identity 求解：$(a^{2}+nb^{2})(c^{2}+nd^{2})=(ac-nbd)^{2}+n(ad+bc)^{2}=(ac+nbd)^{2}+n(ad-bc)^{2}$。

设 $(x_{1},y_{1})$ 是 $x^{2}-ny^{2}=k$ 的最小解，$(x_{2},y_{2})$ 是 $x^{2}-ny^{2}=1$ 的解，那么 $(x_{1}^{2}-ny_{1}^{2})(x_{2}^{2}-ny_{2}^{2})=(x_{1}x_{2}+ny_{1}y_{2})^{2}-n(x_{1}y_{2}+x_{2}y_{1})^{2}=(x_{1}x_{2}-ny_{1}y_{2})^{2}-n(x_{1}y_{2}-x_{2}y_{1})^{2}=k$。从而 $(x_{1}x_{2}+ny_{1}y_{2},x_{1}y_{2}+x_{2}y_{1})$ 和 $(x_{1}x_{2}-ny_{1}y_{2},x_{1}y_{2}-x_{2}y_{1})$ 都是原方程的解。

对于 $ax^{2}-by^{2}=c$ 型的佩尔方程，改写成 $(ax)^{2}-aby^{2}=ac$ 的形式就可以了。

===== 指数循环节 =====

对 $\forall a, b, n \in N^{+}, b \ge \phi(n)$，有 $a ^ {b} \equiv a ^ {b \% \phi(n) + \phi(n)}\pmod{n}$，注意 $b \ge \phi(n)$ 是必要条件，以及式子中取模后指数必须加上 $\phi(n)$，否则结果可能会出错。

===== 威尔逊定理 =====

$$
\prod_{i=1,\gcd(i,m)=1}^{m}i\equiv\begin{cases}
&-1&(m=1,2,4,p^{l},2p^{l},\text{ p is odd prime})\\
&1&(\text{otherwise})
\end{cases}\pmod{m}
$$

===== 类欧几里得算法 =====

设 $f(a,b,c,n,t_{1},t_{2})=\sum_{i=0}^{n}i^{t_{1}}\lfloor\frac{ai+b}{c}\rfloor^{t_{2}}$，求解这一函数值的算法称为类欧几里得算法。这里仅讨论 $6$ 个参数均为非负整数的情况，且定义 $0^{0}=1$：

定义 $m=\lfloor\frac{an+b}{c}\rfloor$，$g_{t}(x)=(x+1)^{t}-x^{t}=\sum_{i=0}^{t-1}g_{ti}x^{i}$，$h_{t}(x)=\sum_{i=1}^{x}i^{t}=\sum_{i=0}^{t+1}h_{ti}x_{i}$。

  * 若 $t_{2}=0$，有：

$$
原式=h_{t_{1}}(n)+[t_{1}=0]
$$

  * 若 $m=0$，有：

$$
原式=0
$$

  * 若 $a=0$，有：

$$
原式=\lfloor\frac{b}{c}\rfloor^{t_{2}}(h_{t_{1}}(n)+[t_{1}=0])
$$

  * 若 $a\ge c$ 或 $b\ge c$，有：

$$
原式=\sum_{u_{1}+u_{2}+u_{3}=t_{2}}{t_{2}\choose u_{1},u_{2},u_{3}}(\lfloor\frac{a}{c}\rfloor)^{u_{2}}(\lfloor\frac{b}{c}\rfloor)^{u_{3}}f(a\%c,b\%c,c,n,t_{1}+u_{2},u_{1})
$$

  * 若 $0\le a,b<c$，有：

$$
原式=m^{t_{2}}h_{t_{1}}(n)-\sum_{u=0}^{t_{2}-1}\sum_{v=0}^{t_{1}+1}g_{t_{2}u}h_{t_{1}v}f(c,c-b-1,a,m-1,u,v)
$$

特别地，若 $t_{1}=0,t_{2}=1$，则有：

  * 若 $m=0$，有：

$$
原式=0
$$

  * 若 $a=0$，有：

$$
原式=\lfloor\frac{b}{c}\rfloor(n+1)
$$

  * 若 $a\ge c$ 或 $b\ge c$，有：

$$
原式=\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor+(n+1)\lfloor\frac{b}{c}\rfloor+f(a\%c,b\%c,c,n)
$$

  * 若 $0\le a,b<c$，有：

$$
原式=nm-f(c,c-b-1,a,m-1)
$$

[[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$ 的个数。这一结论等价于，若 $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|证明]]

====== 线性代数 ======

矩阵的秩等于它最大的非零子式的阶数。对称矩阵的秩等于它最大的非零主子式的阶数（即选取同样的行和列）。[[https://www.jstor.org/stable/1968047|对称矩阵情况下的证明]]，好难找啊。。

====== 抽象代数 ======

===== 有限群中元素的幂 =====

设 $G$ 为一有限群。令 $|G|=n$，对于 $G$ 的每个元素 $a$ 有 $a^{n}=e$ 。

====== 计算几何 ======

===== 球面几何 =====

设球冠的高为 $h$，半径为 $R$，则表面积为 $2\pi Rh$。

球面三角形的面积为 $(A+B+C-\pi)R^{2}$ 。

球面正弦定理：$\frac{\sin A}{a} = \frac{\sin B}{b} = \frac{\sin C}{c}$

球面余弦定理：$\cos a=\cos b\cos c+\sin b\sin c\cos A$, $\cos A=-\cos B\cos C+\sin B\sin C\cos a$

===== 皮克定理 =====

设有一格点多边形，其面积 $S=a+\frac{b}{2}-1$，其中 $a$ 表示多边形内部的整点数，$b$ 表示多边形边界上的整点数。

===== 直线反演 =====

将 $y=kx+b$ 反演到 $(-k,b)$，将 $(k,b)$ 反演到 $y=-kx+b$。这样，两点共线反演为两条直线交于一点，该点是原直线反演出的点。

===== 笛卡尔定理 =====

假设有四个两两相切的圆，设第 $i$ 个的曲率为 $k_{i}=\pm\frac{1}{r_{i}}$，当该圆与其它圆相外切时，曲率为正，否则为负。那么有 $2\sum_{i=1}^{4}k_{i}^{2}=(\sum_{i=1}^{4}k_{i})^{2}$。推广到 $n$ 维，有 $n\sum_{i=1}^{n+2}k_{i}^{2}=(\sum_{i=1}^{n+2}k_{i})^{2}$。

===== 其它 =====

简单多边形中的抛物线长度可以用有向线段来计算。

极角排序后扫描线可以分成上下两个半平面后归并。

有理坐标正多边形只有正方形一种。

三角形的垂心、外心、重心和九点圆圆心共线，其中九点圆圆心到垂心和外心的距离相等，而且重心到外心的距离是重心到垂心距离的一半。

====== 图论 ======

===== 其它 =====

一个森林内部节点的度数平方和等于 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}$
====== 其它 ======

===== 拉格朗日插值法 =====

对某个多项式函数，已知有给定的 $k+1$ 个取值点： $(x_{0},y_{0}),\cdots,(x_{k},y_{k})$ ，则有 $L(x)=\sum\limits_{i=0}^{k}y_{i}l_{i}(x)$ ，其中每个 $l_{i}(x)$ 为拉格朗日基本多项式，其表达式为 $l_{i}(x)=\prod\limits_{j=0,j\neq i}^{k}\frac{x-x_{j}}{x_{i}-x_{j}}$

===== 牛顿迭代法 =====

$x_{n+1}=x_{n}-\frac{f(x_{n})}{f'(x_{n})}$

===== Stern-Brocut tree =====

设有一棵无限的区间树，根结点所表示的区间为$[\frac{0}{1}, \frac{1}{0}]$ ，设父结点所表示的区间为 $[\frac{a}{b},\frac{c}{d}]$ ，则它的左右孩子分别表示 $[\frac{a}{b},\frac{a+c}{b+d}]$ 和 $[\frac{a+c}{b+d},\frac{c}{d}]$ ，这棵树不重不漏地表示了所有正的既约的有理数。

===== Tree of primitive Pythagorean triples =====

设有一棵无限的满三叉树，根结点表示列向量 $(3,4,5)^{T}$ ，设有三个矩阵 $$
A=\begin{pmatrix}
1&-2&2\\
2&-1&2\\
2&-2&3\\
\end{pmatrix}
$$

$$
B=\begin{pmatrix}
1&2&2\\
2&1&2\\
2&2&3\\
\end{pmatrix}
$$

$$
C=\begin{pmatrix}
-1&2&2\\
-2&1&2\\
-2&2&3\\
\end{pmatrix}
$$

设父结点的向量为 $\alpha$，则它从左到右的三个孩子的向量分别为 $A\alpha, B\alpha, C\alpha$，这棵树不重不漏地枚举完了所有基本毕达哥拉斯三元组（$a^{2}+b^{2}=c^{2}$）。

===== 最大反链 =====

给定一个非负整数数列 $\{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|证明]]

===== 矩阵乘法 =====

设 $\oplus,\otimes$ 为二元运算，且 $\oplus$ 满足交换律和结合律，$\otimes$ 满足结合律，$\otimes$ 对 $\oplus$ 满足分配律。定义新的矩阵乘法 $A_{n,m}\times B_{m,p}=C_{n,p}$，其中 $c_{i,j}=\bigoplus_{k=1}^{m}a_{i,k}\otimes b_{k,j}$，那么这种矩阵乘法满足结合律。除了通常的 $\oplus$ 代表加法和 $\otimes$ 代表乘法外，$\oplus$ 代表取最大/最小值，$\otimes$ 代表加法；在 $[0,+\infty)$ 上定义 $\oplus$ 代表取最大/最小值，$\otimes$ 代表乘法，都满足条件。其中后两者对一些求最优值的 ''%%dp%%'' 优化有一定的作用。[[matrix_multiplication|证明]]

===== gcc内建二进制函数 =====

  * ''%%__builtin_popcount(x)%%'' 表示 $x$ 二进制中 $1$ 的个数。
  * ''%%__builtin_parity(x)%%'' 表示 $x$ 二进制中 $1$ 的个数的奇偶性。
  * ''%%__builtin_clz(x)%%'' 表示 $x$ 二进制中前导 $0$ 的个数。
  * ''%%__builtin_ctz(x)%%'' 表示 $x$ 二进制中结尾 $0$ 的个数。
  * ''%%__builtin_ffs(x)%%'' 表示 $x$ 二进制中右起第一个 $1$ 的位置。

以上函数传入的参数为 ''%%unsigned int%%''，如需对 ''%%unsigned long long%%'' 使用，需要在函数名的最后加上 ''%%ll%%''，如 ''%%__builtin_popcountll%%''。''%%__builtin_clz(x)%%'' 和 ''%%__builtin_ctz(x)%%'' 两者在 $x=0$ 时未定义

===== 一类关于集合的计数问题 =====

设有两个集合 $A,B\subset\mathbb{N}$，且 $0\in A,1\in B,|A|=n,|B|=m$。定义 $A+B=\{x+y|x\in A,y\in B\}$，若 $A+B=[1,nm]\cap\mathbb{N}^{+}$，则称 $(A,B)$ 是好的。问这样的集合对有多少个。

这一问题的答案为：

$$
\begin{cases}
&1&(n=1\lor m=1)\\
&f(n,m)+f(m,n)&(n>1\land m>1)
\end{cases}
$$

其中 $f(n,m)=\sum_{i=1}^{+\infty}g_{i}(n)(g_{i}(m)+g_{i+1}(m))$，$g_{i}(n)$ 表示将 $n$ 分解成 $i$ 个大于 $1$ 的数的乘积的方案数（有序）。[[set_counting|证明]]

===== 加法链 =====

对于一个正整数 $n$，它的一个加法链是一个序列 $v_{0},\cdots,v_{s}$，其中 $v_{0}=1,v_{s}=n$，对于所有的 $v_{1},\cdots,v_{s}$，它们都是前面某两个数的和。一种常见的较短的加法链即为快速幂对指数的拆分方法。设 $n$ 的二进制表示下 $1$ 的个数为 $v(n)$，那么使用快速幂的加法链的长度为 $\lfloor\log_{2}n\rfloor+v(n)-1$。另外，设 $n$ 最短的加法链长度为 $l(n)$，$Knuth$ 猜想 $l(n)\ge\lfloor\log_{2}n\rfloor+\lceil\log_{2}v(n)\rceil$，且这一猜想对 $v(n)\le8$ 已经得到证明。

===== 高斯数值积分 =====

求一个 $[-1,1]$ 上的积分，可以使用高斯积分。它近似等于 $\sum_{i=1}^{n}w_{i}f(x_{i})$，当 $f(x)$ 可以用不超过 $2n-1$ 次的多项式近似时，此方法精度较高。下面对 $n=1\sim5$ 列出 $w$ 和 $f$ 的表。

^  $n$  ^                         $x_{i}$                         ^             $w_{i}$             ^
|  $1$  |                           $0$                           |               $2$               |
|  $2$  |                 $\pm\frac{1}{\sqrt{3}}$                 |               $1$               |
|  $3$  |                           $0$                           |          $\frac{8}{9}$          |
|       |                 $\pm\sqrt{\frac{3}{5}}$                 |          $\frac{5}{9}$          |
|  $4$  |  $\pm\sqrt{\frac{3}{7}-\frac{2}{7}\sqrt{\frac{6}{5}}}$  |    $\frac{18+\sqrt{30}}{36}$    |
|       |  $\pm\sqrt{\frac{3}{7}+\frac{2}{7}\sqrt{\frac{6}{5}}}$  |    $\frac{18-\sqrt{30}}{36}$    |
|  $5$  |                           $0$                           |        $\frac{128}{225}$        |
|       |      $\pm\frac{1}{3}\sqrt{5-2\sqrt{\frac{10}{7}}}$      |  $\frac{322+13\sqrt{70}}{900}$  |
|       |      $\pm\frac{1}{3}\sqrt{5+2\sqrt{\frac{10}{7}}}$      |  $\frac{322-13\sqrt{70}}{900}$  |

若积分区间不是 $[-1,1]$，那么需要变换积分区间：$\int_{a}^{b}f(x)\mathbb{d}x=\frac{b-a}{2}\int_{-1}^{1}f(\frac{b-a}{2}x+\frac{a+b}{2})\mathbb{d}x$