组合数学（待补充）
有人问，组合数学不是就一些简单的公式吗？不是的，其实组合数学是数学中的一个非常庞大的分支，接下来就举一些例子。（更新中） 本文主要讲各种数据范围下，求组合数的方式；以及球盒模型各种情况下的公式；最后是一些球盒模型的扩展情况。 转到：球盒模型公式 转到：球盒模型扩展公式 （下面部分标题里的LaTeX公式更新后炸了，就凑合着看吧） 求组合数 以下所有范围都可以当成是以下题目的某个Subtask： 给你 $p$，代表模数。 之后会给你一个 $q$，代表询问次数。 每次询问给定 $n$ 和 $m$，问 $C_n^m \bmod p$ 的值。 下面不给定 $q$ 的范围，因为不重要。 以下全部默认 $n \geq m$。 范围1：$n,m \leq 2000,p \leq 10^9+7$ 先递推预处理，然后直接回答询问即可。 递推式：$C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$。 预处理复杂度：$O(n^2)$ 查询复杂度：$O(1)$ 范围2：$n,m \leq 10^6,p \leq 10^9+7,p\text{ is prime}$ 1 先预处理阶乘，然后直接回答询问即可。 回答询问式：$C_n^m=\dfrac{n!}{m!(n-m)!}$。 为了节省时间复杂度，此处还可以预处理一下阶乘的逆元。 2 预处理复杂度：$O(n)$ 查询复杂度：$O(1)$ 范围3：$n,m \leq 10^6,p \leq 10^9+7$ 1 可以发现，范围2与范围3唯一的不同就是，范围3把质数的条件去掉了。 而把质数的条件后，就没法求逆元了，因为逆元可能不存在。 所以我们考虑换做法。 2 我们考虑把模数做个质因数分解，变成 ${p_1}^{a_1} \times {p_2}^{a_2} \times {p_3}^{a_3} \times \dots \times {p_k}^{a_k}$。 ...