lucas 定理用于求解模数很\(**\)的组合数求解，比如模小素数，会遇到不一定互质即没有逆元的情况。
\[C_{n}^m\equiv C_{n/p}^{m/p}⋅C_{n\mod{p}}^{m\mod{p}}
\]
或者说 \((n_i,m_i)\) 是 \((n,m)\) 在 \(p\) 进制上的一组，\(C_{n_i}^{m_i}\) 的积就是答案力（（（
int p, mul[MN], inv[MN];
mul[0]=inv[0]=1;
mul[1]=inv[1]=1;
for(int i=2; i<p; ++i) mul[i]=mul[i-1]*i%p;
for(int i=2; i<p; ++i) inv[i]=inv[p%i]*(p-p/i)%p;
for(int i=2; i<p; ++i) inv[i]=inv[i-1]*inv[i]%p;
int c(int a,int b,int p) {
if(a<b) return 0;
return (mul[a]*inv[b]%p)*inv[a-b]%p;
}
int lucas(int a,int b,int p) {
if(b==0) return 1;
int lucas(a/p,b/p,p)*c(a%p,b%p,p)%p;
}
想变得可爱的话，可以这么写 qwq
int p, mul[MN], inv[MN];
mul[0]=inv[0]=1;
mul[1]=inv[1]=1;
for(int i=2; i<p; ++i) mul[i]=mul[i-1]*i%p;
for(int i=2; i<p; ++i) inv[i]=inv[p%i]*(p-p/i)%p;
for(int i=2; i<p; ++i) inv[i]=inv[i-1]*inv[i]%p;
int c(int a,int b,int p) {
if(a<b) return 0;
return (mul[a]*inv[b]%p)*inv[a-b]%p;
}
int lucas(int a,int b,int p) {
if(a<b) return 0;
int res=1;
for( ; a; a/=p, b/=p)
res=res*c(a%p,b%p,p)%p;
return res;
}
拓展 lucas
目前并没有学习。