1.排列组合
定义\(P^m_n=\displaystyle\frac{n!}{(n-m)!}\)
\(C^m_n=\displaystyle\frac{n!}{(n-m)!m!}\)
二项式定理：
\((x+y)^n=\displaystyle\sum^{n}_{i=0}=x^iy^{n-i}\times C^i_n\)
Lucas定理
\(C_n^m\equiv(C^{m/p}_{n/p})(C^{m\bmod p}_{n\bmod p})(\bmod p)\)
常见的组合问题
（来自Krydom）
第二个图片解释：对于zcysky的第一个问题，我们可以看作是在空位中插入“隔板”，插入 \(m-1\) 个，而恰好 \(n-1\) 个空位。
第二个问题，我们可以额外手动分配 \(1\) 个，给所有人。转化为问题 \(1\)。
Min-Max容斥
对于一个集合\(T\)，\(p_i\)为其每一单位时间出现概率，\(E(x)\)为\(x\)出现的期望步数。
\(E(min(T))\)为第一个元素出现的期望步数。\(max\)亦然。
\(P(\min(T))=\displaystyle\sum^{}_{i\in T}p_i\)
\(E(\min(T))=\displaystyle\frac{1}{P(\min(T))}\)
\(E(\max_k(S))=\displaystyle\sum_{T\in S}(-1)^{|T|-k}\times E(\min(T))\times C_{|T|-1}^{k-1}(T\neq\emptyset)\)
\(E(\min_k(S))=\displaystyle\sum_{T\in S}(-1)^{|T|-k}\times E(\max(T))\times C_{|T|-1}^{k-1}(T\neq\emptyset)\)
组合问题的解法
1.DP。
过河卒的解法显然行不通。
Krydom的PPT：话说CRT怎么求我也不会
容斥
可以用总方案减去三点共线的方案数。