首页 > 代码库 > Lucas定理及其应用
Lucas定理及其应用
Lucas定理这里有详细的证明。
其实就是针对n, m很大时，要求组合数C(n, m) % p, 一般来说如果p <= 10^5,那么就能很方便的将n，m转化为10^5以下这样就可以按照乘法逆元的方法求解。
定义：
C(n, m) = C(n%p, m%p)*C(n/p, m/p) (mod p)
一种比较好理解的证明方式是这样的， 上面资料中有提到，
由p为质数，(1+x)^p = 1+x^p (mod p) p为质数，然后就是下面这幅图的内容了。
将n, m分别表示成p进制，n = n/p*p+a0, m = m/p*p+b0;
那么对于上面式子x^m的系数，左右两部分肯定是相等的，左边系数C(n, m) ， 而m = m/p*p+b0, 那么i和j分别对应m/p, 和bo
所以就可以得到证明：C(n, m) = C(n%p, m%p)*C(n/p, m/p) (mod p)。
下面就是具体题目了：
HDU
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 using namespace std; 5 6 #define N 100010 7 8 long long mod_pow(int a,int n,int p) 9 {10 long long ret=1;11 long long A=a;12 while(n)13 {14 if (n & 1)15 ret=(ret*A)%p;16 A=(A*A)%p;17 n>>=1;18 }19 return ret;20 }21 22 long long factorial[N];23 24 void init(long long p)25 {26 factorial[0] = 1;27 for(int i = 1;i <= p;i++)28 factorial[i] = factorial[i-1]*i%p;29 //for(int i = 0;i < p;i++)30 //ni[i] = mod_pow(factorial[i],p-2,p);31 }32 33 long long Lucas(long long a,long long k,long long p) //求C(n,m)%p p最大为10^5。a,b可以很大！34 {35 long long re = 1;36 while(a && k)37 {38 long long aa = a%p;long long bb = k%p;39 if(aa < bb) return 0; //这个是最后的改动！40 re = re*factorial[aa]*mod_pow(factorial[bb]*factorial[aa-bb]%p,p-2,p)%p;//这儿的求逆不可先处理41 a /= p;42 k /= p;43 }44 return re;45 }46 47 int main()48 {49 int t;50 cin >> t;51 while(t--)52 {53 long long n,m,p;54 cin >> n >> m >> p;55 init(p);56 cout << Lucas(n+m,m,p) << "\n";57 }58 return 0;59 }
Lucas定理及其应用
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。