此版本已废弃，请移步dokuwiki

博弈论

威佐夫游戏

有两堆石子，两人轮流取，每次可以从一堆中取若干颗石子，也可以从两堆中取一样多的石子。负态为 \(\{\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积还具有如下的性质：

• 对全体自然数 \(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\) 。

模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)\)

其它

\(\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) \]

证明

其他

\(x^{2}+y^{2}=t\) 的整数解的个数为 \(4(\sigma_{1}(t)-\sigma_{3}(t))\)，其中 \(\sigma_{1}(t)\) 表示 \(t\) 的约数中模 \(4\) 余 \(1\) 的个数，\(\sigma_{3}(t)\) 表示 \(t\) 的约数中模 \(4\) 余 \(3\) 的个数。

设有 \(m\) 个正整数 \(c_{1},c_{2},\cdots,c_{m}\)，且严格递增。所有大于等于 \(c_{m-1}c_{m}\)，且能被 \(\gcd(c_{1},c_{2},\cdots,c_{m})\) 整除的整数可以用这 \(m\) 个数使用非负整系数线性表示。证明

线性代数

矩阵的秩等于它最大的非零子式的阶数。对称矩阵的秩等于它最大的非零主子式的阶数（即选取同样的行和列）。对称矩阵情况下的证明，好难找啊。。

抽象代数

有限群中元素的幂

设 \(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}\)。

其它

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

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

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

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

其它

拉格朗日插值法

对某个多项式函数，已知有给定的 \(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}\}\)，那么偏序集 \(\prod_{i=1}^{n}\{x|0\le x\le t_{i},x\in\mathbb{Z}\}\) 的最大反链的大小等于关于 \(x_{i}\) 的不定方程 \(\displaystyle{\sum_{i=1}^{n}x_{i}=\lfloor\frac{\sum_{i=1}^{n}t_{i}}{2}\rfloor}\) 的非负整数解的个数。

矩阵乘法

设 \(\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 优化有一定的作用。证明

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\) 的数的乘积的方案数（有序）。证明

加法链

对于一个正整数 \(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\)