首页 > 代码库 > 【模版】卢卡斯定理

【模版】卢卡斯定理

2024-10-15 13:58:39   216人阅读

给定n,m,p

求 技术分享(m改为n)

C表示组合数。

一个测试点内包含多组数据。

输入输出格式

输入格式：

第一行一个整数T，表示数据组数

第二行开始共T行，每行三个数n m p，意义如上

输出格式：

共T行，每行一个整数表示答案。

输入输出样例

输入样例#1：
2
1 2 5
2 1 5
输出样例#1：
3
3

Lucas定理是用于处理组合数取模的定理

通常用于解决阶乘无法解决的问题。

技术分享

 技术分享

cm(a,b)=a!*(b!*(a-b)!)^(p-2)mod p

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 long long p,a[1000001];
 7 long long qpow(int x,int m)
 8 {
 9     if (m==0) return 1;
10     long long tmp=qpow(x,m/2);
11     tmp=(tmp*tmp)%p;
12     if (m%2==1) tmp=(tmp*x)%p;
13     return tmp;
14 }
15 long long getc(int n,int m)
16 {
17     if (n<m) return 0;
18     if (m>n-m) m=n-m;
19     return (a[n]*qpow(a[m],p-2))%p*qpow(a[n-m],p-2)%p;
20 }
21 long long lucas(int n,int m)
22 {
23     if (m==0) return 1;
24      return (getc(n%p,m%p)*lucas(n/p,m/p)%p);
25 }
26 int main()
27 {int n,m,T;
28 int l,i;
29     cin>>T;
30     for (l=1;l<=T;l++)
31     {
32         scanf("%d%d%d",&n,&m,&p);
33         a[0]=1;
34         for (i=1;i<=p;i++)
35         a[i]=(a[i-1]*i)%p;
36         printf("%lld\n",lucas(n+m,n));
37     }
38 }

【模版】卢卡斯定理


联系
我们