Lucas(卢卡斯)定理
Whiteying
2018-10-08 09:28:21
# 背景 :
C(n,m)用C(n, m) = C(n - 1，m) + C(n - 1, m - 1)的公式来递推时间爆炸。
# 目的 :
求C(n,m) mod p
# 条件：
p为素数
# 表达式：
C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p。（可以递归）
# 递归方程：
(C(n%p, m%p)*Lucas(n/p, m/p))%p。（递归出口为m==0，return 1）
# 核心代码：
```cpp
ll pow_quick(ll a, ll b)
{
ll ans =1;
while(b)
{
if(b &1) ans = ans * a % p;
b>>=1;
a = a*a % p;
}
return ans;
}
ll C(ll n, ll m)
{
if(m > n) return 0;
ll ans = 1;
for(ll i=1; i<=m; i++)
{
ll a = (n+i-m)%p;
ll b = i%p;
ans = (ans*(a*pow_quick(b,p-2)%p))%p;
}
return ans;
}
ll Lucas(ll n, ll m )
{
if(m ==0) return 1;
else return (C(n%p, m%p)*Lucas(n/p, m/p))%p;
}
```