lucas定理

• Z时代
• 2024-01-10
• 分类：综合

组合数太大&&被一个素数取模

公式：

Lucas(n,m)=C(n,m) %p =C(n %p,m %p )∗Lucas(n/p,m/p))%p

　　递推边界----------Lucas(i,0)=1

int C(int n,int m)
{
int ans=1;
for(int i=1;i<=m;++i)
    ans*=(n-m+i)*inv[i]%p;
return ans;
} 
int lucas(int n,int m)
{
if(m==0) return1;
elsereturn C(n%p,m%p)*lucas(n/p,m/p)%p;
}

以上是 lucas定理 的全部内容， 来源链接： utcz.com/z/509363.html