待填。。
计数问题
在一个有\(n\)个点的完全图(complete graph)中有多少棵生成树
对每个\(n>0\)，\({1,2,\cdots,n}\)上的完全图恰好有\(n^{n-2}\)棵生成树。
证明见《具体数学（第二版）》7.6 指数型生成函数。
**[Update] **这不就是Prufer序列的结论吗= =。
排列组合
1. 当 \(C_n^m\) 为奇数时，\((n\&m)==m\)
证明：因为是\(\mod 2\)，所以考虑Lucas定理。
在\(\mod 2\)的情况下\(C(n,m)\)最后只会化成4种情况: \(C(0,1),C(0,0),C(1,0),C(1,1)\),后三种情况都是1，\(C(0,1)\)不存在(0)，所以如果\(C(n,m)\mod 2\)为偶数，那么一定在Lucas的过程中出现了\(C(0,1)\)。
\(\mod 2\)的过程容易想到位运算。
由\(C(n,m)\mod 2=C(n\%2,m\%2)*C(n/2,m/2)=C(n\&1,m\&1)*C(n>>1,m>>1)\) 可知，若\(C(n,m)\)为奇数，那么\(m\)一定是\(n\)二进制1的子集。
2. $$\sum_{i=0}n\frac{1}{i!(n-i)!}=\frac{2n}{n!}$$
https://www.cnblogs.com/SovietPower/p/9425230 （这好像是某组合公式吧）
3. Catalan数应用扩展
https://blog.csdn.net/qq_33435265/article/details/68954205
4. 组合数的各种性质及定理
https://blog.csdn.net/litble/article/details/75913032
数论
1. 计算\(n!\)中质因子p的个数的公式（\(\varepsilon_{p}(n!)\)）
\]
递归式为$$f(n)=f(\left\lfloor\frac{n}{p}\right\rfloor)+\left\lfloor\frac{n}{p}\right\rfloor$$
for(LL i=n; i; i/=p) k+=i/p;
应用：分解阶乘的质因数，如BZOJ1005、CF 1114C、扩展Lucas。
可由\(\varepsilon_2(n!)\)推广到任意素数\(p\)？即$$\varepsilon_p(n!)=\left\lfloor\frac{n}{p}\right\rfloor +\left\lfloor\frac{n}{p^2}\right\rfloor +\left\lfloor\frac{n}{p^3}\right\rfloor +\cdots=\sum_{k\geq1}\left\lfloor\frac{n}{p^k}\right\rfloor$$
\(\varepsilon_p(n!)\)有多大？从求和式中直接去掉底，然后对无穷几何级数求和，可以得到一个简单（然而很好的）上界：
\(\begin{aligned}\varepsilon_p(n!)&<\frac{n}{p}+\frac{n}{p^2}+\frac{n}{p^3}+\cdots\\&=\frac{n}{p}\left(1+\frac{1}{p}+\frac{1}{p^2}+\cdots\right)\\&=\frac{n}{p}\left(\frac{p}{p-1}\right)\\&=\frac{n}{p-1}\end{aligned}\)
——from 《具体数学（第二版）》
有兴趣的还可以看直尺函数(ruler function)。
2. 线性求阶乘逆元
因为\(((n-1)!)^{-1}=(n!)^{-1}*n\)。应用见排列组合2.
inv[n]=FP(fac[n],mod-2);
for(int i=n-1; ~i; --i) inv[i]=inv[i+1]*(i+1)%mod;