① 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定理.待补.
