bzoj 2982 combination——lucas模板

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2982

明明是lucas定理裸题……

非常需要注意C( )里  if ( n<m ) return 0; ！！！！！

可以预处理阶乘和其逆元，也可以现求。现求阶乘逆元的话，可以把 jc[m] 和 jc[n-m] 乘起来再放到pw里。

#include<iostream>

#include<cstdio>

#include<cstring>

#define ll long long

using namespace std;

const int mod=;

int T,n,m,jc[mod+],ans;

int pw(int x,int k)

{

  int ret=;while(k){if(k&)(ret*=x)%=mod;x=(ll)x*x%mod;k>>=;}return ret;

}

void init()

{

  jc[]=;

  for(int i=;i<mod;i++)jc[i]=jc[i-]*i%mod;

}

int C(int n,int m)

{

  if(n<m)return ;//

  return (ll)jc[n]*pw(jc[m]*jc[n-m],mod-)%mod;//jc[m]*jc[n-m]一起求逆元

}

int lucas(int n,int m)

{

  if(!m)return ;

  if(n<mod&&m<mod)return C(n,m);

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

}

int main()

{

  init();

  scanf("%d",&T);

  while(T--)

    {

      scanf("%d%d",&n,&m);

      printf("%d\n",lucas(n,m));

    }

  return ;

}

现求阶乘逆元

#include<iostream>

#include<cstdio>

#include<cstring>

#define ll long long

using namespace std;

const int mod=;

ll n,m;

int T,jc[mod+],jcn[mod+],ans;

int pw(int x,int k)

{

  int ret=;while(k){if(k&)(ret*=x)%=mod;(x*=x)%=mod;k>>=;}return ret;

}

void init()

{

  jc[]=;

  for(int i=;i<mod;i++)jc[i]=jc[i-]*i%mod;

  jcn[mod-]=pw(jc[mod-],mod-);

  for(int i=mod-;i>=;i--)jcn[i]=jcn[i+]*(i+)%mod;

}

int C(int n,int m)

{

  if(n<m)return ;////

  return jc[n]*jcn[m]%mod*jcn[n-m]%mod;

}

int lucas(ll n,ll m)

{

  if(!m)return ;

  if(n<mod&&m<mod)return C(n,m);

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

}

int main()

{

  init();

  scanf("%d",&T);

  while(T--)

    {

      scanf("%lld%lld",&n,&m);

      printf("%d\n",lucas(n,m));

    }

  return ;

}