参考资料
一、 概念
\(\dbinom{n}{m}\) 表示从 \(n\) 个小球内拿 \(m\) 个的方案数，小球一样但顺序不一样算同一种方案，可用 \(\dbinom{n}{m}=\frac{n!}{m!(n-m)!}\) 计算，称为组合。
\(A_n^m\) 表示从 \(n\) 个小球内拿 \(m\) 个的方案数，小球一样但顺序不一样算不同方案，\(A_n^m=\frac{n!}{(n-m)!}\)称为排列。
二、 实现
1. 递推
可以用 dp 的方式理解这种处理方式，令 dp[i][j] 表示前 \(i\) 个球里拿 \(j\) 个的方案数，那么对于当前这个球，不拿的方案数是 dp[i-1][j]，拿的方案数是 dp[i-1][j-1]。这样得出递推式 dp[i][j]=dp[i-1][j]+dp[i-1][j-1]
2. 阶乘逆元
根据组合数的求法直接用 \(m!\) 的逆元乘上 \((n-m)\) 的逆元再乘上 \(n!\) 即可。
3. Lucas 定理
当模数不是质数时便可以考虑 Lucas 定理，
\(\dbinom{n}{m}=\dbinom{n\bmod p}{m\bmod p}\times\dbinom{n/p}{m/p}\)
三、其他
1. 二项式定理
\((a+b)^n=\sum\limits_{i=0}^n\dbinom{n}{i}a^{n-i}b^i\)
2. 插板法
典型应用有错排问题等，在推一些组合数学问题结论上比较好用，个人认为 OI-Wiki 上已经讲的十分清楚了，推荐去那学习。有时间再补吧（