组合‌$C_{?}^{?}$：从n个元素中取出m个元素，不考虑顺序，只关注元素的组合方式。例如，从A、B、C中取出两个元素，AB和BA被视为同一个组合。

‌排列‌$A_{?}^{?}$：从n个元素中取出m个元素，考虑顺序。例如，AB和BA被视为不同的排列。

---

$A_{1}^{1} = 1$

$A_{n}^{1} = n$

$A_{n}^{n} = n! = n * (n - 1) * …… * 1$

$A_{m}^{n}= \frac{A_{m}^{m}}{A_{n}^{n}} = \frac{m!}{(m - n)!}=m * (m - 1) * …… * (m - n + 1)$ $A_{m}^{n}=m*A_{m-1}^{n-1}$

---

$C_{1}^{1} = 1$

$C_{n}^{1} = n$

$C_{n}^{n} = 1$

$C_{m}^{n} = \frac{A_{m}^{n}}{A_{n}^{n}} = \frac{m!}{n!*(m - n)!} = C_{m}^{m - n}$

$C_{m}^{n} = C_{m - 1}^{n - 1} + C_{m - 1}^{n}考虑第m个元素选或者不选$

$C_{m}^{n} = C_{m}^{n - 1} * \frac{m - n + 1}{n} 提问：这些公式有除法怎么保证一定结果是整数？提示：因式分解$

---

数据规模大m!/n!的乘法过程中必然发生溢出，一般会要求模运算简单参考 组合数学与递推 最美数学系列-什么是费马小定理以及如何证明它？ 最基础的是利用快速幂和费马小定理求乘法逆元 $a*a^{-1} \equiv 1(mod p),(a,p)=1互质$

$a^{p-1}\equiv 1 (mod p)\Rightarrow a*a^{p-2}\equiv 1 (mod p)\Rightarrow a^{-1} \equiv a^{p-2}(mod p)$

---

加法逆元$a+a^{-1} \equiv 0(mod p)$ 经典例子，n位补码：$a+!a+1\equiv2^{n}$

$2^{n}\equiv0(mod p)\Rightarrow a^{-1}=!a+1=-a补码$

---

实在估不明白$\log_{2}{n}$具体耗时，可以用对数换底公式,注意大部分语言log默认自然底数e为base。设$a=e^x，b=e^y\Rightarrow x=\ln a, y=\ln b$

$\log_{a}{b}=\log_{e^x}{e^y}=b\log_{e^x}{e}=\frac{xy\log_{e^x}{e}}{x}=\frac{y\log_{e^x}{e^x}}{x}=\frac{y}{x}=\frac{\ln b}{\ln a}$

>>> import math
>>> math.log(10)
2.302585092994046
>>> math.log10(10)
1.0
>>> math.log(math.e)
1.0
>>> math.log(1E7)/math.log(2)#log2 1E7
23.25349666421154
>>> math.log(1E30)/math.log(2)#log2 1E30所以倍增、分治的log威力很强大
99.65784284662087