【模板】卢卡斯定理

题目

洛谷P3807卢卡斯定理

题解

若p是质数,则对于任意整数1<=m<=n:

如果要多次询问组合数的值,就需要预处理一些值。

注意用了Lucas定理后,可能出现C(0,0)的情况,令它为1。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月28日 下午4:11

【小白解析】
此题主要还是根据数学理论发展。第13行的乘法逆元计算来自之前的模板。可以证明若(a*b)%p==1,则对任意x/a为整数时,(x/a)%p==(x*b)%p,在此不多赘述。
因此累乘s2即可达到阶乘倒数的效果。