Lucas定理模板
2019-08-16 08:01:42来源:博客园 阅读 ()
Lucas定理模板
一本通上不是很懂,所以自己查资料做了个总结。
Lucas定理:若p是质数,则对于任意整数1<=m<=n,有:
c(n,m)%p=c(n%p,m%p)*c(n/p,m/p)%p
也就是把n和m表示成p进制数,对p进制下的每一位分别计算组合数,最后再乘起来。
最后一句话可能难以理解,实际上联想到平常求一个十进制数的二进制数,也是对十进制数进行不断取模,由除以二的余数得到二进制数,所以对于Lucas定理也差不多是一个道理。
由于计算过程中不断地取模,同时事实上c(n/p,m/p)仍可以拆分,所以主要用于组合数中n,m较大时的问题中。
模板题
【问题描述】
给出组合数c(n,m),表示从n个元素中选出m个元素的方案数。例如c(5,2)=10,c(4,2)。可是当n,m比较大的时候,c(n,m)很大!于是小波希望你输出c(n,m)mod p的值。
【输入格式】
输入数据第一行是一个正整数T,表示数据组数(T<=100)。
接下来是T组数据,每组数据有3个正整数n,m,p(1<=m<=n<=109,m<=104,m<p<109,p是质数)。
【输出格式】
对于每组数据,输出一个正整数,表示c(n,m)mod p的结果。
【样例输入】
2
5 2 3
5 2 61
【样例输出】
1
10
分析
可以看到题目中的数据范围1<=m<=n<=109,m<=104,m<p<109,(再结合这是一道Lucas模板题),所以可以很轻松的分析出这道题用普通递推是过不了的,所以就要用到我们的Lucas定理哒。
首先根据前文的分析可以打出主函数和Lucas的函数部分。
主函数:
int main() { scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&p); printf("%d\n",Lucas(n,m)); } return 0; }
Lucas:
ll Lucas(ll n,ll m)//注意本题数据范围过大要开long long { if(!m) return 1;//一个很容易理解的特判 else return (c(n%p,m%p)*Lucas(n/p,m/p))%p; }
接下来主要分析c(n%p,m%p)的求解。
我们知道c(n,m)=n!/[m!(n-m)!]=[n*(n-1)*...*(n-m+1)]/m!,也就是说,只要我们能够分别求解[n*(n-1)*...*(n-m+1)]和m!,那么就可以得到问题的答案。但是!别忘了还有取模计算!当涉及取模运算的计算中,如果有除法,不能直接除以一个数,而是变成乘以它的乘法逆元。(如果有不知道乘法逆元的朋友慢慢往后看应该能够意会的,或者可以问度娘)
(关于这句话个人理解是因为两数相除会有除不尽的情况,不方便取模。又因a*b%c=(a%c*b%c)%c,所以可求出乘法逆元。如有曲解烦请指出qwq)
这里主要介绍利用费马小定理求解乘法逆元
费马小定理:如果p是一个质数,而整数a不是p的倍数,则有a^(p-1)≡1(mod p)
记住这句话!!!(p.s. a≡b(mod n)相当于a被n整除余数为b的意思)
先来继续前面的分析。当我们除以一个数n时,也就是乘上1/n,所以我们可以假设x为1/n关于模n的逆元,则有x≡1/n(mod p),即x*n≡1(mod p)。看到这里可以发现这个式子有一半跟费马小定理一模一样!而通过题目已知p为质数(做题中大部分情况下p也都为质数),所以我们可以直接套用费马小定理!
得到:x*n=n^(p-1),即x=n^(p-2)!
所以只要运用这个结论,再结合快速幂,就可以轻松求解哒。
求解c(n%p,m%p)部分:
ll C(ll n,ll m) { if(m>n) return 0; ll a=1,b=1; for(ll i=n-m+1;i<=n;++i) a=a*i%p; for(ll i=2;i<=m;++i) b=b*i%p; return a*quickpow(b,p-2)%p; }
费马小定理和快速幂求解乘法逆元部分:
ll quickpow(ll a,ll b) { ll s=1; while(b) { if(b&1) s=s*a%p; a=a*a%p; b>>=1; } return s; }
所以这道其实很简单的模板题就能被我们轻松掌握啦。
完整代码:
#include<iostream> #include<cstdio> #define ll long long using namespace std; ll p; ll quickpow(ll a,ll b) { ll s=1; while(b) { if(b&1) s=s*a%p; a=a*a%p; b>>=1; } return s; } ll C(ll n,ll m) { if(m>n) return 0; ll a=1,b=1; for(ll i=n-m+1;i<=n;++i) a=a*i%p; for(ll i=2;i<=m;++i) b=b*i%p; return a*quickpow(b,p-2)%p; } ll Lucas(ll n,ll m) { if(!m) return 1; else return (C(n%p,m%p)*Lucas(n/p,m/p))%p; } int main() { ll n,m; int t; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&p); printf("%d\n",Lucas(n,m)); } return 0; }
希望能对大家对自己有一定的帮助吧qwq
部分资料源于度娘,如有错误或侵权烦请指出~
原文链接:https://www.cnblogs.com/ninecities/p/11344994.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- C++ 模板类vector 2020-05-31
- C++ 模板类array 2020-05-31
- C++ 模板类vector 2020-05-30
- 单调队列模板【附例题】 2020-05-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash