Lucas定理
C
n
m
m
o
d
p
=
C
n
/
p
m
/
p
×
C
n
m
o
d
p
m
m
o
d
p
m
o
d
p
C_n^m \mod p=C_{n/p}^{m/p} \times C_{n\mod p}^{m\mod p} \mod p
C
n
m
m
o
d
p
=
C
n
/
p
m
/
p
×
C
n
m
o
d
p
m
m
o
d
p
m
o
d
p
，p为素数
Lucas板子
int qpow(ll b,int n,int mod)
{
int res=1;
while(n)
{
if(n&1) res=1ll*res*b%mod;
b=1ll*b*b%mod;
n>>=1;
}
return res;
}
int fac[maxn];
void init(int p)
{
fac[0]=fac[1]=1;
for(int i=2;i<=p;++i)
fac[i]=1ll*fac[i-1]*i%p;
}
int C(int n,int m,int p)
{
if(m>n) return 0;
return 1ll*fac[n]*qpow(1ll*fac[m]*fac[n-m]%p,p-2,p)%p;
}
int Lucas(ll n,ll m,int p)
{
int ans=1;
while(n&&m&&ans)
{
ans=1ll*ans*C(n%p,m%p,p)%p;
n/=p;
m/=p;
}
return ans;
}
组合数计算
取模时，需要注意 n < m 的情况，此时为 0
1、线性推逆元，在只需要初始化一次的时候使用比较好
const int N=5e5;
int fac[N+10],finv[N+10];
void init()
{
fac[0]=fac[1]=1;
for(int i=2;i<=N;++i)
fac[i]=1ll*fac[i-1]*i%mod;
finv[N]=qpow(fac[N],mod-2,mod);
for(int i=N-1;i>=0;--i)
finv[i]=1ll*finv[i+1]*(i+1)%mod;
}
int C(int n,int m)
{
return 1ll*fac[n]*finv[m]%mod*finv[n-m]%mod;
}
2、推出阶乘之后，用费尔马小定理计算逆元
int fac[maxn];
void init(int p)
{
fac[0]=fac[1]=1;
for(int i=2;i<=p;++i)
fac[i]=1ll*fac[i-1]*i%p;
}
int C(int n,int m,int p)
{
if(m>n) return 0;
return 1ll*fac[n]*qpow(1ll*fac[m]*fac[n-m]%p,p-2,p)%p;
}
3、直接用组合式公式计算
ll C(ll a,ll b,ll p)
{
if(a<b) return 0;
if(a==b) return 1;
if(b>a-b) b=a-b;
ll ca=1,cb=1;
for(int i=0;i<b;++i)
{
ca=(ca*(a-i))%p;
cb=cb*(i+1)%p;
}
return ca*qpow(cb,p-2,p)%p;
}
4、不需要取模时，用杨辉三角
ll C[1000][1000];
void init()
{
C[0][0]=1;
for(int i=1;i<=500;++i)
{
C[i][0]=C[i][i]=1;
for(int j=1;j<=i-1;++j)
C[i][j]=C[i-1][j-1]+C[i-1][j];
}
}
Saving Beans HDU – 3037
链接:http://acm.hdu.edu.cn/showproblem.php?pid=3037
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5,maxm=1e5+5;
int qpow(ll b,int n,int mod)
{
int res=1;
while(n)
{
if(n&1) res=1ll*res*b%mod;
b=1ll*b*b%mod;
n>>=1;
}
return res;
}
int fac[maxn];
void init(int p)
{
fac[0]=fac[1]=1;
for(int i=2;i<=p;++i)
fac[i]=1ll*fac[i-1]*i%p;
}
int C(int n,int m,int p)
{
if(m>n) return 0;
return 1ll*fac[n]*qpow(1ll*fac[m]*fac[n-m]%p,p-2,p)%p;
}
int Lucas(ll n,ll m,int p)
{
int ans=1;
while(n&&m&&ans)
{
ans=1ll*ans*C(n%p,m%p,p)%p;
n/=p;
m/=p;
}
return ans;
}
int t,n,m,p;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&p);
init(p);
printf("%d\n",Lucas(n+m,m,p));
}
return 0;
}