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

2018-06-17 21:38:46来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目背景

这是一道模板题。

题目描述

给定n,m,p(1\le n,m,p\le 10^51n,m,p105)

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

保证P为prime

C表示组合数。

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

输入输出格式

输入格式:

 

第一行一个整数T(T\le 10T10),表示数据组数

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

 

输出格式:

 

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

 

输入输出样例

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

卢卡斯定理
$C(n,m)%p=C(n%p,m%p)*C(n/p,m/p)$
对于这道题来说,p是素数,解逆元的时候用快速幂

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #define LL long long 
 6 using namespace std;
 7 const LL MAXN=1e6+10;
 8 const LL INF=0x7fffff;
 9 inline LL read()
10 {
11     char c=getchar();LL flag=1,x=0;
12     while(c<'0'||c>'9')    {if(c=='-')    flag=-1;c=getchar();}
13     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*flag;
14 }
15 LL js[MAXN];
16 LL fastpow(LL a,LL p,LL mod)
17 {
18     LL base=1;
19     while(p)
20     {
21         if(p&1)    base=(base*a)%mod;
22         a=(a*a)%mod;
23         p>>=1;
24     }
25     return base;
26 }
27 LL C(LL n,LL m,LL mod)
28 {
29     if(m>n)    return 0;
30     return js[n]*fastpow(js[m],mod-2,mod)*fastpow(js[n-m],mod-2,mod)%mod;
31 }
32 LL Lucas(LL n,LL m,LL mod)
33 {
34     if(m==0)    return 1;
35     else return C(n%mod,m%mod,mod)*(Lucas(n/mod,m/mod,mod))%mod;
36 }
37 int main()
38 {
39     LL T=read();
40     js[0]=1;
41     while(T--)
42     {
43         LL n=read(),m=read(),mod=read();
44         for(LL i=1;i<=mod;i++)    js[i]=(js[i-1]*i)%mod;
45         printf("%lld\n",Lucas(n+m,m,mod)%mod);
46     }
47     return 0;
48 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:震惊!Vector两行代码求逆序对,六行代码过普通平衡树

下一篇:Day3晚笔记