百度百科对于组合数的定义是：从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。 由于经常遇到一些组合数问题，所以整理一些常见的快速求组合数的方法，附上Python的实现代码。

( n m ) = n ! m ! ∗ ( n − m ) ! \binom {n}{m}=\frac {n!}{m!*(n-m)!} (mn​)=m!∗(n−m)!n!​ 可以直接调用math.factorial求得阶乘，然后算出组合数，如下：

输入：

输出：

( n m ) = ( n − 1 m − 1 ) + ( n − 1 m ) \binom {n}{m}=\binom {n-1}{m-1}+\binom {n-1}{m} (mn​)=(m−1n−1​)+(mn−1​) 递归出口就在于当n=m或者m=1的时候。

输入：

输出：

前面的两种方法，在n,m数字很大的时候，运行时间会很长。在介绍第三个方法之前，先来介绍几个概念，不当之处，欢迎指点。

百度百科：同余定理数论中的重要概念。给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。

取模运算的等价变形适合加法、减法、乘法 ( a + b ) % p = ( a % p + b % p ) % p (a + b) \% p = (a \% p + b \% p) \% p