Python快速求组合数C(n,m)三种方法整理
百度百科对于组合数的定义是：从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。
由于经常遇到一些组合数问题，所以整理一些常见的快速求组合数的方法，附上Python的实现代码。
一、m,n不是特别大的时候：
(
n
m
)
=
n
!
m
!
∗
(
n
−
m
)
!
\binom {n}{m}=\frac {n!}{m!*(n-m)!}
(mn)=m!∗(n−m)!n!
可以直接调用math.factorial求得阶乘，然后算出组合数，如下：
import math
n,m = map(int,input().split())
print(math.factorial(n)//(math.factorial(m)*math.factorial(n-m)))
输入：
5 3
输出：
10
二、用定义式递归：
(
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 = map(int,input().split())
def rec(n,m):
if m == n:
return 1
elif m == 1:
return n
else:
return rec(n-1,m-1)+rec(n-1,m)
print(rec(n,m))
输入：
10 3
输出：
120
三、逆元+快速幂思想参考大佬
前面的两种方法，在n,m数字很大的时候，运行时间会很长。在介绍第三个方法之前，先来介绍几个概念，不当之处，欢迎指点。
（1）、同余定理
百度百科：同余定理数论中的重要概念。给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。
5 ≡ 3(mod 2) #5和 3对模2同余
（2）、模的加减乘除运算
取模运算的等价变形适合加法、减法、乘法
(
a
+
b
)
%
p
=
(
a
%
p
+
b
%
p
)
%
p
(a + b) \% p = (a \% p + b \% p) \% p
(a+b)%p=(a%p+b%p)%p
(
a
−
b
)
%
p
=
(
a
%
p
−
b
%
p
)
%
p
(a - b)\% p = (a\% p - b\% p) \% p
(a−b)%p=(a%p−b%p)%p
(
a
∗
b
)
%
p
=
(
a
%
p
∗
b
%
p
)
%
p
( a * b) \% p = (a \% p * b \% p) \% p
(a∗b)%p=(a%p∗b%p)%p
但是，取模运算的等价变形不符合除法
a
/
b
%
p
≠
(
a
%
p
/
b
%
p
)
%
p
a/b \% p ≠ (a\%p / b\%p) \% p
a/b%p=(a%p/b%p)%p
比如：
（
100
%
20
）
%
11
=
5
%
11
=
5
（100 \% 20）\% 11 = 5 \% 11 = 5
（100%20）%11=5%11=5
（
100
%
11
/
20
%
11
)
%
11
=
(
1
/
9
)
%
11
=
0
%
11
=
0
（100\%11 / 20\%11) \% 11 = (1 / 9) \% 11 = 0 \% 11 = 0
（100%11/20%11)%11=(1/9)%11=0%11=0
（3）、逆元
逆元：对于a和p，若a和p互素且
(
a
∗
b
)
%
p
≡
1
(a * b) \% p ≡ 1
(a∗b)%p≡1
则称b为a%p的逆元。
假设c为b%p的逆元，即 b ∗ c % p = 1 b*c\%p=1 b∗c%p=1
(
a
/
b
)
%
p
(a / b) \% p
(a/b)%p
=
(
a
/
b
)
∗
1
%
p
= (a / b) * 1 \% p
=(a/b)∗1%p
=
(
a
/
b
)
∗
(
b
∗
c
%
p
)
%
p
=(a/b)*(b*c\%p)\%p
=(a/b)∗(b∗c%p)%p
=
a
∗
c
%
p
=a*c\%p
=a∗c%p
=
(
a
%
p
)
∗
(
c
%
p
)
%
p
=(a\%p)*(c\%p)\%p
=(a%p)∗(c%p)%p
这样就把求 ( a / b ) % p (a / b) \% p (a/b)%p转化成一个 ( a % p ) ∗ ( c % p ) % p (a\%p)*(c\%p)\%p (a%p)∗(c%p)%p乘法问题。
（4）、费马小定理
百度百科：费马小定理(Fermat’s little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有 a ( p − 1 ) % p ≡ 1 a ^ {(p-1)} \% p ≡ 1 a(p−1)%p≡1。
a
（
p
−
1
）
=
a
（
p
−
2
）
∗
a
a^{（p-1）}=a^{（p-2）} * a
a（p−1）=a（p−2）∗a
所以有
a
（
p
−
2
）
∗
a
%
p
≡
1
a^{（p-2）} * a\%p≡1
a（p−2）∗a%p≡1
所以
a
（
p
−
2
）
%
p
a^{（p-2）}\%p
a（p−2）%p是
a
a
a的逆元。
由于m,n很大，现在要求的是
(
n
m
)
%
p
\binom{n}{m}\%p
(mn)%p，假设
p
p
p取100000007，由于取模运算的等价变形不适用于除法，即：
(
n
m
)
%
p
≠
n
!
%
p
m
!
%
p
∗
(
n
−
m
)
!
%
p
%
p
\binom{n}{m}\%p≠ \frac{n!\%p}{m!\%p*(n-m)!\%p}\%p
(mn)%p=m!%p∗(n−m)!%pn!%p%p
根据上面求得：
(
a
/
b
)
%
p
=
(
a
%
p
)
∗
(
c
%
p
)
%
p
(a / b) \% p=(a\%p)*(c\%p)\%p
(a/b)%p=(a%p)∗(c%p)%p
c
是
b
%
p
的
逆
元
。
c是b\%p的逆元。
c是b%p的逆元。
就相当于我们要求出
m
!
和
(
n
−
m
)
!
{m!和(n-m)!}
m!和(n−m)!的逆元，根据
a
（
p
−
2
）
%
p
a^{（p-2）}\%p
a（p−2）%p是
a
a
a的逆元，得到
m
!
的
逆
元
是
m
!
(
p
−
2
)
m!的逆元是m!^{(p-2)}
m!的逆元是m!(p−2)
(
n
−
m
)
!
的
逆
元
是
(
n
−
m
)
!
(
p
−
2
)
(n-m)!的逆元是(n-m)!^{(p-2)}
(n−m)!的逆元是(n−m)!(p−2)
所以
(
n
m
)
%
p
=
[
n
!
%
p
∗
(
m
!
(
p
−
2
)
%
p
)
∗
(
(
n
−
m
)
!
(
p
−
2
)
%
p
)
]
%
p
\binom{n}{m}\%p=[n!\%p*(m!^{(p-2)}\%p)*((n-m)!^{(p-2)}\%p)]\%p
(mn)%p=[n!%p∗(m!(p−2)%p)∗((n−m)!(p−2)%p)]%p
下面用代码来实现：
import math
n,m = map(int,input().split())
p = 100000007
def power(x,y): #求x的y次方
p = 100000007
res = 1
while y:
if y % 2 != 0:
res *= (x%p)
y >>= 1
x *= (x%p)
return res
a = (math.factorial(n))%p
b = (power(math.factorial(m),(p-2)))%p
c = (power(math.factorial(n-m),(p-2)))%p
print(a*b*c%p)
中间的power函数是用快速幂做的，直接用Python的运算符“**”的话会非常大，会超时。
小白欢迎大佬指点~