① 1 <= m <= n <= 5000

1.1 如果 m,n非常小以至于C(n,m)都不会爆long long ,那么我们直接上杨辉三角去解

1.2 如果 n , m 比较大，但是要求取模,还是用杨辉三角去解。

1.3 如果 保证了最终的结果不爆long long ,那么我们可以用记忆化搜索 + 杨辉三角.

注意:最好要用记忆化搜索去写，用一行一行刷表式的去递推会造成中间的爆long long,导致程序不规范.

用记忆化搜索(递归)不会造成爆long long 的原理:C(n,m) = C(n-1,m-1) + C(n - 1 , m).如果大问题不爆long long. 那么小问题一定不会爆long long ,那么我们就自顶向上的用记忆化搜索去写。


②  n <= 1e6(也可以更大),单点询问,不取模,保证结果不会爆long long

思路:

有了这个公式，我们动态维护一个ans表示当前的组合数，对于相邻的下一个组合数.设fz = n - x + 1.fm = x;

令A = gcd(fm,ans),用A除去fm和ans.

令B = gcd(fz,fm),用B除去fm和fz.

剩下来的fm一定是1.因为任意组合数C(n,x)是整数，所以ans * fz 一定能够整除fm.

这样以来可以保证只要结果不爆long long,那么计算过程中也不会爆long long.(这个计算的过程实际上是先算C(n,1),然后转移的算C(n,2) .... 再算到C(n,m),这个过程中ans一定是递增的).

复杂度:O(nlogn)

③ n <= 1e6.单点查询，要求在模mod意义下的值.

思路:

分母分子分别求出来，对分母求逆元再相乘得结果.复杂度O(n).(这里可以有个优化，O(n)计算阶乘的逆元).

④ n ,m 极大(通常远大于mod),要求在模mod意义下的值.(mod <= 1e5 且保证mod是质数).

思路:

引入Lucas定理，递归求解.复杂度:

板子:

http://acm.hdu.edu.cn/viewcode.php?rid=32753896

⑤跟上述一样，但mod不一定是质数.

引入扩展Lucas定理.待补.