FZUOJ2020 組合 (lucas定理)

 Problem 2020 組合

Accept: 705    Submit: 1706

Time Limit: 1000 mSec    Memory Limit : 32768 KB

 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的值！

 Input

輸入資料第一行是一個正整數T,表示資料組數 (T <= 100) 接下來是T組資料，每組資料有3個正整數 n, m, p (1 <= m <= n <= 10^9, m <= 10^4, m < p < 10^9, p是素數)

 Output

對于每組資料，輸出一個正整數，表示C(n,m) mod p的結果。

 Sample Input

25 2 35 2 61

 Sample Output

110

 Source

FOJ有獎月賽-2011年04月（校賽熱身賽）

解析：裸的lucas定理。 代碼：

#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long LL;

LL reverse(LL a,LL m)
{
  if(a==0)return 0;
  LL y=0,x=1,r=a%m,q,t,mm=m;
  if(r<0)r+=m;
  while((m%r)!=0)
    {
      a=m,m=r,q=a/m,r=a%m;
      t=x,x=y-x*q,y=t;
	}
  if(r!=1)return 0;
  if(x<0)x+=mm;
  return x;
}

LL C(LL n,LL m,LL p)
{
  LL i,j,k=min(m,n-m),ans=1;
  for(i=n-k+1;i<=n;i++)ans=ans*i%p;
  for(i=2;i<=k;i++)ans=ans*reverse(i%p,p)%p;
  return ans;
}

LL lucas(LL n,LL m,LL p)
{
  if(m==0)return 1;
  return C(n%p,m%p,p)*lucas(n/p,m/p,p)%p;
}

int main()
{
  LL i,j,k,t,n,m,p;
  scanf("%I64d",&t);
  while(t--)
    {
      scanf("%I64d%I64d%I64d",&n,&m,&p);
      printf("%I64d\n",lucas(n,m,p));
	}
  return 0;
}