Problem Description

给出组合数C(n,m), 表示从n个元素中选出m个元素的方案数。例如C(5,2) = 10, C(4,2) = 6.可是当n,m比较大的时候，C(n,m)很大！于是xiaobo希望你输出 C(n,m) mod p的值！

思路：水题，练一下ｌｕｃａｓ

 

#include<iostream>

#include<cstdio>

#include <math.h>

#include<algorithm>

#include<string.h>

#include<queue>

#define MOD 1000003

#define maxn 2009

#define LL long long

using namespace std;

LL mpow(LL a,LL n,LL p)

{

        if(n==0)return 1;

        if(n==1)return a%p;

        if(n&1)return (a*mpow(a,n-1,p))%p;

        else

        {

                LL u=mpow(a,n>>1,p)%p;

                return (u*u)%p;

        }

}

LL C(LL n,LL m,LL p)

{

        if(m==0)return 1;

        if(m>n-m)m=n-m;

        LL up=1,down=1;

        for(int i=1;i<=m;i++){

                up=(up*(n-i+1))%p;

                down=(down*i)%p;

        }

        return up*mpow(down,p-2,p)%p;

}

long long lucas(long long n,long long m,long long p)

{

        if(m==0)return 1;

        return C(n%p,m%p,p)*lucas(n/p,m/p,p);

}

int main()

{

        long long m,n,p;

        int t;

        scanf("%d",&t);

        while(t--)

        {

                scanf("%I64d%I64d%I64d",&n,&m,&p);

                printf("%I64d\n",lucas(n,m,p));

        }

        return 0;

}