洛谷 P3807 【模板】卢卡斯定理-白红宇

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

阅读量：6971 次

发布时间：2019-06-27

本文共 1478 字，大约阅读时间需要 4 分钟。

题目背景

这是一道模板题。

题目描述

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

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

保证P为prime

C表示组合数。

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

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

输入样例#1：

21 2 52 1 5

输出样例#1：

卢卡斯定理

$C(n,m) \% p = C(n \% p, m \% p) * C(n / p, m / p)$

对于这道题来说，p是素数，解逆元的时候用快速幂

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            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 }