如何求组合数——列举一系列组合数的求法

· · 个人记录

观前提示：点赞留名关注即可享受一键三联的快感

本篇博客专为初学者（包括作者自己）定制，有一切问题均可留言或私信作者，也希望看到本篇博客的大佬萌能为本蒟蒻提出各种建议。

前置知识

乘法逆元

组合数

快速幂

温馨提示:已下所有组合数运算皆在模意义下进行

学习完组合数后，我们应该会意识到组合数的应用范围极广，大部分的数学题中都存在着它的影子。一般在遇到这些数学题的时候，我们都会采取预处理组合数的方案来优化程序。（初学者做题时，如果实时求组合数，在大部分情况下都会超时）那么有哪些预处理组合数的方案呢？

小组合数

这应该是最普遍、最基础的组合数求法。初学者在学习组合数时，会学到这么一个公式：\boxed{C_n^m=C_{n-1}^m+C_{n-1}^{m-1}} 。这就相当于告诉了我们一个组合数的求法：如果将组合数放到一个二维数组中，用A_{n,m}表示组合数C_n^m，则\boxed{A_{n,m}=A_{n-1,m}+A_{n-1,m-1}}。由此，便可以很简单地预处理组合数，时间复杂度为O(nm)。

代码如下。

typedef long long ll;
ll c[1005][1005];
void init(int n,int m){
    for (int i=0;i<=n;i++){
        c[i][0]=1;
        for (int j=1;j<=i && j<=m;j++){
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        }
    }
}

然而，这种方法的时间复杂度毕竟是O(nm)的，在很多题目上都会超时，适用范围不是非常广泛，因此称其为小组合数，但仍然值得初学者学习并加以理解。

下面将提供出时间复杂度更小的预处理方案。

2020年6月3号更新内容：

大组合数

虽然这种方案的名字与上一种方案（小组合数）十分相似，但却是两种完全不同的方案。

这种预处理组合数的方案需要利用到另外一个关于组合数的基本公式：\boxed{C_n^m=\frac{n!}{m!(n-m)!}}，我们可以发现：如果我们提前将阶乘部分预处理好，那么求出C_n^m的速度就会明显比我们的上一种方案（即小组合数）更快。因此，在这里我们只需用O(n)的时间复杂度快速地预处理阶乘，再根据公式，就能够以O(\log n)的时间复杂度（因为分母部分需要求逆元）计算组合数。

代码如下：

const int N=5000;(范围根据题目要求改变)
ll fac[N];
ll ksm(ll x,ll n){
    ll res=1;
    while(n>0){
        if (n&1) res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}//快速幂
void com_init(int n){
    fac[0]=1;
    for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
}//预处理阶乘
ll com(int n,int m){
    if (n<m || m<0) return 0; //使所求的组合数有意义
    return fac[n]*ksm(fac[n-m],mod-2)%mod
                 *ksm(fac[m],mod-2)%mod; 
}

现在，我们已经能够以O(\log n)的时间计算一个组合数，读者们是否觉得这种方法十分的简单、快捷？然而，对于“大组合数”的讲解并没有结束。

我们已经知道：“大组合数”的预处理方案是因为逆元的存在，才会以O(\log n)的时间复杂度进行计算。那么，这是否意味着我们可以在逆元方面进行进一步的优化呢？答案是肯定的。不过，该怎样在逆元方面进行进一步的优化呢？

机智的读者们可能已经猜到了：既然阶乘可以预处理，那么我们也可以对逆元进行预处理。而对于逆元的预处理，在这里作者并没有用一些奇特的方法（原因是作者也不会），只是简单的模拟了逆元的运算，并将其累乘（这样做可以避免使用快速幂，而快速幂的时间复杂度是O(\log n)的）,这下，我们便能以O(1)的时间复杂度求出组合数。

代码如下：

cosnt int N=5000;(范围根据题目要求改变）
ll fac[N];
ll ie[N],inv[N]; 
void inv_init(int n){
    inv[1]=1;
    for (int i=2;i<=n;i++){
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    }
}
void com_init(int n){
    inv_init(n);
    ie[0]=fac[0]=1;
    for (int i=1;i<=n;i++){
        fac[i]=fac[i-1]*i%mod;
        ie[i]=ie[i-1]*inv[i]%mod;
    }
}
ll com(int n,int m){
    if (n<m || m<0) return 0;
    return fac[n]*ie[n-m]%mod*ie[m]%mod;
}

2020年6月27日更新内容

递推求逆元

这里提供一个短小而精悍的求逆元的方法，直接上代码：

ll NY(ll x) {
    if (x==1) return 1;
    return (mod-mod/x)*NY(mod%x)%mod;
}

不过这种方法并不是在任何情况下都适用，因为它的时间复杂度非常玄学，有兴趣的读者可以在知乎查找相关讨论。

未完待续.....