奇奇怪怪

奇妙的知识

数论

$gcd(x, y, z) = gcd(x, y - x, z - y)$ ，这启发我们，对于已知数列 $\{a\}$ 及其差分数列 $\{b\}$ ， $gcd(a_i, a_{i+1}, …, a_j) = gcd(a_i, b_{i+1}, …, b_j)$
$C_{a}^{b}=C_{a-1}^{b-1}+C_{a-1}^{b}$ ，这启发我们可以用递推求组合数
自然数次幂求和：
$$
\begin{aligned}
& \sum_{i = 1}^{n} i = \frac{1}{2} n (n + 1) \\
& \sum_{i = 1}^{n} i^2 = \frac{1}{6} n (n + 1) (2n + 1) \\
& \sum_{i = 1}^{n} i^3 = \frac{1}{4} n^2 (n + 1)^2 \\
& \sum_{i = 1}^{n} i^4 = \frac{1}{30} n (n + 1) (2n + 1) (3n^2 + 3n - 1) \\
& \sum_{i = 1}^{n} i^5 = \frac{1}{12} n^2 (n + 1)^2 (2n^2 + 2n - 1) \\
& \sum_{i = 1}^{n} i^6 = \frac{1}{42} n (n + 1) (2n + 1) (3n^4 + 6n^3 - 3n + 1) \\
\end{aligned}
$$

对于自然数 $k$ 次幂求和，明显其结果是一个关于 $n$ 的 $k + 1$ 次多项式，可以待定系数法求解
对于 $a^x \equiv 1 \pmod n$ ，有解当且仅当 $\gcd(a, n) = 1$ ，且最小整数解 $x$ 一定满足 $x \mid \varphi(n)$ ；证明可以设 $\varphi(n) = kx + r$ ，发现 $r$ 小于 $x$ 且 $a^r \equiv 1 \pmod n$ ，只可能 $r = 0$
错排公式： $D(n) = n! * (1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + … + (-1)^n \frac{1}{n!})$ 或者

$D(n) = (n - 1)(D(n - 1) + D(n - 2))$ ， $D(0) = 1, D(1) = 0$
卡特兰数：

$Cat(n) = \frac{C_{2n}^{n}}{n + 1}$

$Cat(n) = C_{2n}^{n} - C_{2n}^{n - 1}$

$Cat(n) = \frac{Cat(n - 1) * (4n - 2)}{n + 1}$

定义：

哈密尔顿通路：经过图中每个结点且仅经过一次的通路

哈密尔顿回路：经过图中每个结点且仅经过一次的回路

哈密尔顿图：存在哈密尔顿回路的图

与欧拉回路的对比：欧拉回路是指不重复地走过所有路径的回路；哈密尔顿回路是指不重复地走过所有点并且最后回到起点的回路

判定：

设其有 $n$ 个顶点， $u, v$ 为图中任意，两个不相邻的顶点

对于一个无重边和自环的有向图，如果其中任意两点间都有且仅有一条边，就称其为竞赛图，顾名思义，它可以想象成 $n$ 个人两两对决，赢得向输的连边

性质：