组合数_牛客博客

求\(n!\)中有多少个质因子p

方法一（非递归）

结论：\(n!\)中有\((\frac{n}{p}+\frac{n}{p^2}+\frac{n}{p^3}+…)\)个质因子p
时间复杂度：\(O(logn)\)

int cal(int n,int p){
    int ans=0;
    while(n--){
        ans+=n/p;
        n/=p;
    }
    return ans;
}

方法二（递归）

结论：\(n!\)中质因子p的个数，实际上等于1~n的倍数的个数\(\frac{n}{p}\)加上\(\frac{n}{p}!\)中质因子p的个数

int cal(int n,int p){
    if(n<p) return 0;
    return n/p+cal(n/p,p);
}

应用：\(n!\)的末尾有几个零即\(n!\)中因子\(10\)的个数，而这又等于\(n!\)中质因子\(5\)的个数**

组合数的计算(记录已经计算过的C(n,m))

\(C_{n}^{m}=C_{n-1}^{m}+C_{n-1}^{m-1}\)

递归

时间复杂度：小于\(O(n^2)\)

long long res[67][67];
long long C(long long n,long long m){
	if(m == 0 || m == n)	return 1;
	if(res[n][m] != 0)	return res[n][m];
	return res[n][m] = C(n-1,m) + C(n-1,m-1);  //赋值给res[n][m]并返回 
}

递推将整张表都计算出来（杨辉三角）

时间复杂度：\(O(n^2)\)

long long res[67][67];
const int N = 60;
void calC(){
	for(int i=0;i<=N;i++){
		res[i][0] = res[i][j] = 1;  //初始化边界 
	}
	for(int i=2;i<=N;i++){
		for(int j=0;j<=i/2;j++){
			res[i][j] = res[i-1][j] + res[i-1][j-1];  //递推计算 C(i,j)
			res[i][i-j] = res[i][j];  //C(i,i-j) = C(i,j)  
		}
	}
}

通过定义式的变形来计算

时间复杂度：\(O(m)\)

long long C(long long n,long long m){
	long long ans = 1;
	for(long long i=1;i <= m;i++){
		ans = ans * (n-m+i) / i;  //注意一定要先乘再除 
	}
	return ans;
}

如何计算\(C_{n}^{m}\)%p

方法一：通过递推公式计算

要求：\(n\leq10000,m\leq10000,p\leq10^9\)

递归：

int  res[1010][1010] = {0};
int C(int n,int m,int p){
	if(m == 0 || m == n)	return 1;  //C(n,0) = C(n,n)=1 
	if(res[n][m] != 0)	return res[n][m];  //已经有值 
	return res[n][m] = (C(n-1,m) + C(n-1,m-1)) % p;  //赋值给res[n][m]并返回 
}

递推：

const int N = 1010;
void calC(){
	for(int i=0;i<=N;i++){
		res[i][0] = res[i][j] = 1;//初始化边界 
	}
	for(int i=2;i<=N;i++){
		for(int j=0;j<=i/2;j++){
			res[i][j] = (res[i-1][j] + res[i-1][j-1]) % p;//递推计算 C(i,j)
			res[i][i-j] = res[i][j];//C(i,i-j) = C(i,j)  
		}
	}
}

方法二：根据定义式计算

要求：\(n\leq10^6,m\leq10^6,p\leq10^9\)
时间复杂度：\(O(klogn)\),其中k为不超过n的质数个数

递归：

//使用筛法得到素数表prime，注意表中最大素数不得小于n
int prime[maxn];

//计算C(n,m)%p
int C(int n,int m,int p){
	int ans = 1;
	//遍历不超过n的所有质数
	for(int i=0;prime[i] <= n;i++){
		//计算C(n,m)中prime[i]的指数c,cal(n,k)为n!中含质因子k的个数
		int c = cal(n,prime[i]) - cal(m,prime[i]) - cal(n-m,prime[i]);
		//快速幂计算prime[i]^c%p
		ans = ans * binaryPow(prime[i],c,p) % p; 
	}	
	return ans;
}

方法三：通过定义式变形来计算

情况① \(m<p\)，且p是素数

要求：\(n\leq10^9,m\leq10^5,m<p\leq10^9\),p是素数
时间复杂度：\(O(mlogm)\)

int C(int n,int m,int p){
	int ans = 1;
	for(int i=1;i <= m;i++){
		ans = ans * (n-m+i) % p;
		ans = ans * inverse(i,p) % p;  //求i模p的逆元 
	}
	return ans;
}

情况② m任意，且p是素数

要求：\(n\leq10^9,m\leq10^5,p\leq10^9\),p是素数
时间复杂度：\(O(mlogn)\)

int C(int n,int m,int p){
	//ans存放计算结果，numP统计分子中的p比分母中的p多几个
	int ans = 1,numP = 0;
	for(int i=1;i<=m;i++){
		int temp = n-m+i;  //分子
		while(temp % p == 0){  //去除分子中的所有p，同时累计numP
			numP++;
			temp /= p; 
		} 
		ans = ans * temp % p;  //乘以分子中除了p以外的部分
		
		temp = i;//分母
		while(temp % p == 0){  //去除分母中的所有p，同时减少numP
			numP--;
			temp /= p; 
		} 
		ans = ans * inverse(temp,p) % p;  //除以分母中除了p以外的部分 
	} 
	if(numP > 0)	return 0;  //分子中p的个数多于分母，直接返回0
	else	return ans;  //分子中p的个数等于分母，返回计算的结果 
}

方法四：Lucas定理

要求：\(n\leq10^18,m\leq10^18,p\leq10^5\),p是素数

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

组合数