大数组合--卢卡斯定理

组合数我们用Cxx来表示，一切尽在代码中。。。

简单说就是一行代码来回捣鼓：

lucas(n, m)%p
=
lucas(n/p, m/p)*C(n%p, m%p)%p

/*
这个是干啥用的呢，有这么一类题，让你求个C54，呵呵简单。
but，我数据范围给你1~1e18，你怎么说！
woc，你tm在玩我，ok你给我这么大数据，无论如何long long都放不开吧。
好，我给你个p，你把结果mod它，行不？
你p给多大？
我给1~1e5，而且p是素数。
好，看我来A掉它！
卢卡斯部分：lucas(n, m)%p
=
lucas(n/p, m/p)
*
C(n%p, m%p)
%p
↑这里是不断优化的卢卡斯
↑这里是优化后的Cxx
↑%p也很重要
首先要明确，卢卡斯定理只不过是这类题型中的一部分，剩下的就是真正去求Cxx，
所以这里求Cxx这一步就可以继续优化了，比如我们已知p为素数，由费马小定理：a^(p-1)=1(mod p)，我们同时除以a，就变成了：a^(p-2)=1/a(mod p)
因为这里的Cxx就是n!/(m!(n - m)!)，所以我们把(m!(n - m)!)换成逆元，加上上面的费马小定理，1/a就可以求出来了。
下面的q_pow函数就是来求逆元滴
*/
#include <iostream>
#include <ctdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int N =1e5;
ll n, m, p, fac[N];
void init()
{
int i;
fac[0] =1;
for(i =1; i <= p; i++)
fac[i] = fac[i-1]*i % p;
//存n!，方便计算
}
ll q_pow(ll a, ll b)
{
ll
ans =1;
while(b)
{
if(b &1)
ans = ans * a % p;
a = a*a % p;
b>>=1;
}
return
ans;
}
ll C(ll n, ll m)
{
if(m > n)
return 0;
return
fac[n]*q_pow(fac[m]*fac[n-m], p-2) % p;
//对分母进行求逆元
}
ll Lucas(ll n, ll m )
{
if(m ==0)
return 1;
else return
(C(n%p, m%p)*Lucas(n/p, m/p))%p;
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%lld%lld%lld", &n, &m, &p);
//分别输入Cnm和%p
init();
printf("%lldn", Lucas(n, m));
}
return 0;
}

最后

以上就是能干乐曲为你收集整理的大数组合--卢卡斯定理的全部内容，希望文章能够帮你解决大数组合--卢卡斯定理所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。