ITKeyword,专注技术干货聚合推荐

注册 | 登录

卢卡斯定理的模板以及应用

qingshui23 分享于 2016-08-04

推荐:组合数学应用-NYOJ743

描述 for(i=1;i<=n;i++)   for(j=i+1;j<=n;j++)     for(k=j+1;k<=n;k++)         operation; 你知道 operation 共执行了多少次吗; 输入 输入 m 和n 表示m为for

2019阿里云全部产品优惠券(新购或升级都可以使用,强烈推荐)
领取地址https://promotion.aliyun.com/ntms/yunparter/invite.html

定义: Lucas定理是用来求 C(n,m) MOD p ,p为素数的值。Lucas定理:我们令 n=sp+q,m=tp+r.(q,r≤p) 那么:(在编程时你只要继续对 调用 Lucas 定理即可。代码可以递归的去完成这个过程,其中递归终点为 t=0 ;时间复杂度 O(logp(n)∗p):) 主要解决当 n,m 比较大的时候,而 p 比较小的时候 <1e6 ,那么我们就可以借助 卢卡斯定理来解决这个问题: 模板: #include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <vector>#include <queue>#include <algorithm>#include <set>using namespace std;typedef long long LL;typedef unsigned long long ULL;const int INF = 1e9+5;const int MAXN = 1e6+5;const int MOD = 1e9+7;const double eps = 1e-7;const double PI = acos(-1);using namespace std;LL quick_mod(LL a, LL b, LL c){

LL ans = 1;

while(b)

{

if(b & 1)

ans = (ans*a)%c;

b>>=1;

a = (a*a)%c;

}

return ans;}LL fac[MAXN];void Get_Fac(LL m)///m!{

fac[0] = 1;

for(int i=1; i<=m; i++)

fac[i] = (fac[i-1]*i) % m;}LL Lucas(LL n, LL m, LL p){

LL ans = 1;

while(n && m)

{

LL a = n % p;

LL b = m % p;

if(a < b)

return 0;

ans = ( (ans*fac[a]%p) * (quick_mod(fac[b]*fac[a-b]%p,p-2,p)) ) % p;

n /= p;

m /= p;

}

return ans;}int main(){

LL n, m, p;

Get_Fac(p);

Lucas(n, m, p);///C(n,m)%p

return 0;} 应用: HDU 3037 题目大意: 求 C(n+m,m) % P AC代码:

推荐:Find a multiple(组合数学:鸽巢原理的简单应用)

Link:http://poj.org/problemid=2356 Find a multiple Time Limit: 1000MS

Memory Limit: 65536K Total Submissions: 7062

Accepted: 3092

Special Judg

/** 2016 - 08 - 04 晚上 Author: ITAK Motto: 今日的我要超越昨日的我,明日的我要胜过今日的我, 以创作出更好的代码为目标,不断地超越自己。 **/#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <vector>#include <queue>#include <algorithm>#include <set>using namespace std;typedef long long LL;typedef unsigned long long ULL;const int INF = 1e9+5;const int MAXN = 1e6+5;const int MOD = 1e9+7;const double eps = 1e-7;const double PI = acos(-1);using namespace std;LL quick_mod(LL a, LL b, LL c){

LL ans = 1;

while(b)

{

if(b & 1)

ans = (ans*a)%c;

b>>=1;

a = (a*a)%c;

}

return ans;}LL fac[MAXN];void Get_Fact(LL m)///m!{

fac[0] = 1;

for(int i=1; i<=m; i++)

fac[i] = (fac[i-1]*i) % m;}LL Lucas(LL n, LL m, LL p){

LL ans = 1;

while(n && m)

{

LL a = n % p;

LL b = m % p;

if(a < b)

return 0;

ans = ( (ans*fac[a]%p) * (quick_mod(fac[b]*fac[a-b]%p,p-2,p)) ) % p;

n /= p;

m /= p;

}

return ans;}int main(){

int T;

scanf("%d",&T);

while(T--)

{

LL n, m, p;

scanf("%I64d%I64d%I64d",&n,&m,&p);

Get_Fact(p);

printf("%I64d\n",Lucas(n+m,m,p));

}

return 0;}

推荐:Lucas定理应用分析——大组合数取模

    首先给出Lucas(卢卡斯)定理:     有非负整数A、B,和素数p,A、B写成p进制为:A=a[n]a[n-1]...a[0],B=b[n]b[n-1]...b[0]。 则组合数C(A,B)与C(a[n],b[n]

定义: Lucas定理是用来求 C(n,m) MOD p ,p为素数的值。Lucas定理:我们令 n=sp+q,m=tp+r.(q,r≤p) 那么:(在编程时你只要继续对 调用 Lucas 定理即可。代码可以递归的去完成这个过程,其

相关阅读排行


用户评论

游客

相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。