您的位置: 首页  >  IT文章  >  洛谷—— P3807 【模板】卢卡斯定理

洛谷—— P3807 【模板】卢卡斯定理

分类: IT文章 • 2022-05-01 16:05:29

https://www.luogu.org/problemnew/show/3807

题目背景

这是一道模板题。

题目描述

给定n,m,p(1le n,m,ple 10^51≤n,m,p≤105)

求 C_{n+m}^{m} mod pCn+mm​ mod p

保证P为prime

C表示组合数。

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

输入输出格式

输入格式：

第一行一个整数T(Tle 10T≤10)，表示数据组数

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

输出格式：

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

输入输出样例

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


 1 #include <cstdio>
 2 
 3 #define LL long long
 4 inline void read(int &x)
 5 {
 6     x=0; register char ch=getchar();
 7     for(; ch>'9'||ch<'0'; ) ch=getchar();
 8     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
 9 }
10 const int N(1e5+5);
11 LL fac[N];
12 
13 inline LL Pow(LL a,int b,int p)
14 {
15     LL ret=1;
16     for(; b; b>>=1,a*=1ll*a,a%=p)
17         if(b&1) ret*=1ll*a,ret%=p;
18     return ret;
19 }
20 
21 inline LL C(LL n,LL m,LL p)
22 {
23     if(n<m) return 0;
24     return fac[n]%p*Pow(fac[m],p-2,p)%p*Pow(fac[n-m],p-2,p)%p;
25 }
26 
27 inline LL lus(LL n,LL m,LL p)
28 {
29     if(m==0) return 1;
30     return C(n%p,m%p,p)*lus(n/p,m/p,p)%p;
31 }
32 
33 int Presist()
34 {
35     int t; read(t); fac[0]=1;
36     for(int n,m,p; t--; )
37     {
38         read(n),read(m),read(p);
39         for(int i=1; i<=n+m; ++i)
40             fac[i]=1ll*fac[i-1]%p*i%p;
41         printf("%lld
",lus(n+m,m,p));
42     }
43     return 0;
44 }
45 
46 int Aptal=Presist();
47 int main(int argc,char**argv){;}

相关推荐