数学问题——组合数

 一、关于 n！的一个问题

　　n! 表示 n 的阶乘，我们讨论一下关于它的一个问题：求 n! 中有多少个质因子 p。

　　举个例子，6! = 1*2*3*4*5*6 ，于是 6! 中有 4 个质因子 2，两个质因子 3。

　　对这个问题，直观的想法是计算 1~n 的每个数各有多少个质因子 p，然后将结果累加，时间复杂度为 O(nlogn)。

　　我们需要寻求速度更快的方法。现在考虑 10! 中质因子 2 的个数，显然 10! 中有 2¹ 的数的个数为 5，有因子 2² 的数的个数为 2，有因子 2³ 的数的个数为 1，因此 10! 中质因子 2 的个数为 5+2+1=8。

　　仔细思考便可发现此过程可以推广为：n! 中有 $left ( frac{n}{p}+frac{n}{p^{2}}+frac{n}{p^{3}}+... ight )$ 个质因子 p。代码如下：

// 计算 n! 中有多少个质因子 p
int cal(int n, int p) {
    int ans = 0;
    while(n) {
        ans += n/p;        // 累加 n/p^k 
        n /= p;
    }
    return ans;
} 

　　利用这个算法，可以很快计算出 n! 的末尾有多少个零：由于末尾 0 的个数等于 n! 中因子 10 的个数，而这又等于 n! 中质因子 5 的个数，因此只需要带入 cal(n,5) 就可以得到结果。

二、组合数的计算

　　组合数 $C_{n}^{m}$ 是指从 n 个不同元素中选出 m 个元素的方案数 (m≤n)，其定义式为 $C_{n}^{m}=frac{n!}{m!left ( n-m ight )!}$ 。本节主要讨论如下两个问题：

1. 1.  如何计算 $C_{n}^{m}$
   2.  如何计算 $C_{n}^{m}\%p$　　　　

　　1. 如何计算 $C_{n}^{m}$

　　方法一：通过定义式直接计算

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

　　由于 $C_{n}^{m}$ 表示从 n 个不同的数中选 m 个数的方案数，因此可以转换为下面两种选法的方案数之和：一是不选最后一个数，从前 n-1 个数中选 m 个数；二是选最后一个数，从前 n-1 个数中选 m-1 个数。于是就可以得到下面这个递推式：

　　　　　　$C_{n}^{m}=C_{n}^{m-1}+C_{n-1}^{m-1}$

　　而由定义可知 $C_{n}^{0}=C_{n}^{n}=1$，这正好可以作为递归的边界，代码如下：

// 计算组合数 Cnm，递归形式 
long long C(long long n, long long m) {
    if(m==0 || n==m)    return 1;
    return C(n-1,m) + C(n-1,m-1);
}

　　以上代码会造成一个问题：重复计算。因此不妨记录下已经计算过的 C(n,m)，这样当下次碰到时就可以作为结果直接返回了，代码如下：

long long res[67][67] = {0};    // 记录结果 
// 计算组合数 Cnm，递归形式 
long long C(long long n, long long m) {
    if(m==0 || n==m)    return 1;
    if(res[n][m] != 0)        // 已经计算过 
        return res[n][m];
    return res[n][m] = C(n-1,m) + C(n-1,m-1);    // 赋值并返回 
} 

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

　　定义式可进行如下化简：

　　　　$C_{n}^{m}=frac{n!}{m!left ( n-m ight )!}=frac{(n-m-1)*(n-m+2)*...*(n-m+m)}{1*2*...*m}=frac{frac{frac{(n-m+1)*(n-m+2)}{2}*...}{...}*(n-m+m)}{m}$

　　代码如下：

// 通过定义式的变形来计算组合数 Cnm 
long long C1(long long n, long long m) {
    long long ans = 1;
    long long i;
    for(i=1; i<=m; ++i) {
        ans = ans * (n-m+i) / i;
    }
    return ans;
}

　　完整测试代码如下：

/*
    组合数的计算 
*/

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>

long long res[67][67] = {0};    // 记录结果 
// 计算组合数 Cnm，递归形式 
long long C(long long n, long long m) {
    if(m==0 || n==m)    return 1;
    if(res[n][m] != 0)        // 已经计算过 
        return res[n][m];
    return res[n][m] = C(n-1,m) + C(n-1,m-1);    // 赋值并返回 
} 

// 通过定义式的变形来计算组合数 Cnm 
long long C1(long long n, long long m) {
    long long ans = 1;
    long long i;
    for(i=1; i<=m; ++i) {
        ans = ans * (n-m+i) / i;
    }
    return ans;
}

int main() {
    long long n, m;
    while(scanf("%lld%lld", &n, &m) != EOF) {
        printf("%lld
", C(n, m));
        printf("%lld
", C1(n, m));
    }

    return 0;
}

　　2. 如何计算 $C_{n}^{m}\%p$

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

　　这种方法基于第一个问题的方法二，只需要在原先的代码中适当的地方对 p 取模即可。代码如下：

int resp[1010][1010] = {0};
// 求组合数 Cnm 对 p 取模，递归 
int Cp(int n, int m, int p) {
    if(m==0 || n==m)    return 1;
    if(res[n][m] != 0)        // 已经计算过 
        return resp[n][m];
    return resp[n][m] = (C(n-1,m) + C(n-1,m-1))%p;    // 赋值并返回 
}