【数论】卢卡斯定理模板 洛谷P3807 【数论】卢卡斯定理模板 洛谷P3807
>>>>题目
【题目】
https://www.luogu.org/problemnew/show/P3807
【输入格式】
第一行一个整数T(Tle 10T≤10)，表示数据组数
第二行开始共T行，每行三个数n m p，意义如上
【输出格式】
共T行，每行一个整数表示答案。
【输入样例】
2
1 2 5
2 1 5
【输出样例】
3
3
>>>>分析
emmmm模板题还是不用分析了吧
卢卡斯定理解决的就是组合数C(n,m)中m，n太大的情况
根据定理的内容，C(n,m)=C(n/p,m/p)*C(n%p,m%p)其中p是模数
我们只需要不断递归求解C(n/p,m/p)就可以啦
因为同余方程不满足两边同时除一个数，那么只能将除一个数转化成乘这个数在模数p意义下的逆元
求逆元的方式有很多种，在我的另一个博客里面会有详细介绍φ(>ω<*)
#include<bits/stdc++.h> #define ll long long #define L I64d #define maxn 100005 using namespace std; ll fac[2*maxn]; int p,T; void init(int n,int m)//预处理阶乘 { fac[0]=1; for(int i=1;i<=n+m;i++) fac[i]=fac[i-1]*i%p; } ll quickpow(ll x,ll y) { ll ans=1; while(y) { if(y&1) ans=ans*x%p; x=x*x%p; y=y>>1; } return ans%p; } ll C(ll m,ll n) { if(m>n) return 0; return fac[n]*quickpow(fac[m],p-2)%p*quickpow(fac[n-m],p-2);//费马小定理求逆元 } ll lucas(ll m,ll n) { if(!m) return 1; return lucas(m/p,n/p)*C(m%p,n%p)%p; } int main() { scanf("%d",&T); while(T--) { int n,m; scanf("%d%d%d",&n,&m,&p); init(); printf("%Ld ",lucas(m,n+m)); } return 0; } /* 2 1 2 5 2 1 5 */
完结撒花✿✿ヽ(°▽°)ノ✿