lucas是求组合数C（m,n）%p,有一个公式：C(m,n) = C(m/p,n/p)*C(m%p,n%p)。
（a*b）%c==a%c*b%c,但是（a/b）%c!=a%c/b%c,所以我们要算b在c意义下的乘法逆元。
一个线性求乘法逆元。a[i] = (p - p / i) * a[p % i] % p;或者是费马小定理，i在p下的逆元就是i^(p - 2)。然后从后往前推。
两种代码：
第一种：
for(int i=2;i<=n+m;i++) a[i]=(p-p/i)*a[p%i]%p;for(int i=2;i<=n+m;i++) a[i]=a[i-1]*a[i]%p;第二种:
for(int i = 1;i <= n;i++) sum[i] = sum[i - 1] * i % p;//阶乘 inv[k] = pow(sum[k],p - 2); for(int i = k - 1;i >= 0;i--) { inv[i] = inv[i + 1] * (i + 1) % p;//阶乘逆元 }然后是lucas：
int lucas(int x,int y) { if(x < y) return 0; else if(x < p) return sum[x] * inv[y] * inv[x-y] % p; else return lucas(x/p,y/p) * lucas(x%p,y%p) % p; }
转载于:https://www.cnblogs.com/DukeLv/p/9123272.html
