卢卡斯定理

卢卡斯定理

用途

卢卡斯((Lucas))定理用于求当(n)、(m)较大时，(C_n^m mod;p(p为质数))的值。

描述

递归形式

对于

[n,m in mathbb{Z},p为质数 ]

有

[C_n^m mod;p=C_{n;mod;p}^{m;mod;p}cdot C_{n/p}^{m/p} mod;p ]

非递归形式

对于

[n,m in mathbb{Z},p为质数\ 设m=prod_{i=0}^{k}m_ip^i,n=prod_{i=0}^{k}n_ip^i ]

有

[C_n^m mod;p=prod_{i=0}^{k}C_{n_i}^{m_i}mod;p ]

使用方法

对于比较大的组合数，我们先利用卢卡斯定理将其拆分，拆分所得到的每个较小的组合数则可以用更简单的方法求解。对于递归形式，拆分出的(C_{n;mod;p}^{m;mod;p})还原成阶乘形式后，由于(p)为质数且除数与(p)互质，我们可以考虑运用费马小定理之类的方法求逆元进行计算。对于非递归形式，相当于把(m)、(n)均当做一个(p)进制下的数，其每一位也与(p)互质，也可以如此计算。

注意边界条件：当(m=0)时，(C_n^m=1)；当(n<m)时，(C_n^m=0)。阶乘可以进行预处理减少重复计算。

代码

//递归
int power(int b,int k)
{
	int base=1;
	while(k)
	{
		if(k&1)
			base=(long long)base*b%p;
		k>>=1;
		b=(long long)b*b%p;
	}
	return base;
}
int inv(int x)
{
	return power(x,p-2);
}
int C(int x,int y)
{
	return (long long)factorial[x]*inv((long long)factorial[y]*factorial[x-y]%p)%p;
}
int Lucas(int x,int y)
{
	if(!y)
		return 1;
	if(x%p<y%p)
		return 0;
	return C(x%p,y%p)*Lucas(x/p,y/p)%p;
}

//非递归
int Lucas(int x,int y)
{
	int result=1;
	while(x&&y)
	{
		if(x%p<y%p)
			return 0;
		result=(long long)result*C(x%p,y%p)%p;
		x/=p;
		y/=p;
	}
	return result;
}