求大的组合数C(n，m)对一些素数pi的乘积取模，n，m <= 10^18，pi <= 10^5，素数的个数不超过10个
先用Lucas求C(n,m) % pi的值，这样就得到了一些对形如 x % p1 = a1，x % p2 = a2，x % p3 = a3，这样就可以对p，和a用中国剩余定理，求出最小的x，这个x就是( n choose m ) % (prod_{p_i} )
Lucas 处理的时候 long long * long long mod m 会爆 long long，可以用慢速乘，慢速乘一定要把非负数放在幂的位置上
Accepted 5446 31MS 1412K 1700 B G++
求C(n, m) % p，(1 <= m <= n <= 10^9, m <= 10^4, m < p < 10^9, p是素数)
数论Lucas定理是用来求 c(n,m) mod p的值,p是素数（从n取m组合，模上p）。
描述为:
Lucas(n, m, p)=cm(n%p, m%p)* Lucas(n/p, m/p, p)
Lucas(x, 0, p)=1;
而
cm(a, b) % p =a! / (b! * (a-b)!) mod p
也 = (a! / (a-b)!) / (b!) mod p
由于 (a/b) mod p = a * b^(p-2) mod p //费马小定理
这里，其实就是直接求 (a! / (a-b)!) * (b!)^(p-2) mod p
以上转自百度百科
FZU 2020 Accepted 208 15 GNU C++ 647
从n棵树上取下不超过m个果子，有多少种取法，对素数p取模 1 <= n, m <= 1000000000, 1 < p < 100000
转化成求 x1 + x2 + x3 +…+ xn = k的解的个数，其中k的范围为0-m，根据插板法，可知，其方案数为C(n + m – 1, k) ?
sum = C(n + m -1, 0) + C(n + m – 1, 1) + C(n + m – 1, 2) + C(n + m – 1, m)
又因为 C(n, m) = C(n – 1, m – 1) + C(n – 1, m)，对sum进行合并
那么 sum = C(n + m, m)然后上Lucas求C(n + m, m) % p
Accepted 3037 514MS 1404K 691 B G++
Gyf's Blog 