求组合数的N种姿势

Posted on 2018-10-09 19:55:10

遇到一道题,题目略去,分析后难点变成求C(n,m) % p,其中 m<1e6 , p = 1e9+7(注意是质数),对ACMer来说肯定是小儿科问题,然而算法弱渣还是被难住了。

姿势一

按照原理暴力计算,
C(n,m) = m! / (m-n)!n!

需要提醒的是,同余的性质中不存在除法的,也就是 (a / b) % p 不等于 (a % p / b % p) % p。
还要继续吗?

恭喜你,你即将喜提成就【实现高精度大数类】。
虽然复杂度是O(m)但并没有什么卵用

姿势二

初中老师教过:

C(n,m) = C(n-1,m-1)+C(n-1,m)

打表,复杂度是O(m^2),然而,m < 1e6,只能过30%的样例,大概也就是1000以内的组合数。当然了姿势一也就只能算到十几。

姿势三

在一的基础上打表素数筛,要比一二好很多,但是过于繁琐了,就没有尝试了。

姿势四

引入一个叫Lucas定理的东东:当p为质数,C(n,m) % p = C(n/p , m/p) * C(n%p , m%p) % p
虽然很高大上,但是我想你也发现了,我们这里 p >> m。。。。。

姿势五

大佬说的暴力。

引入概念逆元

对于正整数 a 和 n ,如果有 x ,那么把这个同余方程中 ax % n = 1 的最小正整数解叫做 a 模 p 的逆元。

而C(n,m) = m! / (m-n)!n! = m(m-1)… * (m - n +1) / n!, 只需要求取 m! 模 p 的逆元x就行啦!

等等,逆元怎么求??

答曰:不会!

Google到方法如下:

待填坑

扩展欧几里得算法

快速幂

递推求1~n的逆元

reference:
segmentfault
SyncShinee
月光森林