【C++】排列与组合算法详解（进阶篇）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

【C++】排列与组合算法详解（进阶篇）

作者：

星河依旧长明 , 2023-05-20 20:16:22 , 所有人可见 , 阅读 238

CSDN:更好的阅读体验

写在前面

我上次发了一篇题解：C++排列与组合算法详解
最开始，我是抱着水题解的想法写的，但却成为了阅读量最高的文章，没有之一。

所以今天咱们来重制一篇文章，介绍几个进阶优化版的算法。

算法1：朴素算法

思路

具体见 C++排列与组合算法详解

缺点

不能将结果取模，因为朴素的组合公式在取模意义下没用。

算法2：递推预处理

思路

我们发现：
$C_a^0 = 1\\ C_a^b=C_{a-1}^b+C_{a-1}^{b-1}(a,b>0)$

所以我们可以写一个递推函数（部分非主要内容已省略）：

void init_C()
{
    for (int i = 0; i < N; i ++ ) // N 表示预处理最大的下标
        for (int j = 0; j <= i; j ++ )
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % P;
}

再预处理阶乘：

void f(int n)
{
    f[0] = 1;
    for (int i = 1; i <= n; i ++ )
        f[i] = (LL)f[i - 1] * i % P;
}

需要排列的话还可以预处理排列：

void init_A(int n)
{
    for (int i = 0; i <= n; i ++ )
        for (int j = 0; j <= i; j ++ )
            a[i][j] = (LL)f[i - j] * c[i][j] % P;
}

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

可以处理 $5000$ 以内规模的数据

算法3：阶乘逆元

思路

根据费马小定理可得，当 $p$ 为质数时， $a^{p-1} \equiv 1\pmod p$
$\therefore a^{p-2} \equiv \frac{1}{a}\pmod p$
这就是乘法逆元，通常使用在需要除法取模的情况。

这里再次提一下排列、组合公式： $C_a^b=\frac{a!}{b!(a-b)!},\ \ A_a^b=\frac{a!}{b!}$

求逆元需要用到快速幂：

LL qpow(LL a, LL b, LL p)
{
    LL res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return res;
}

然后预处理阶乘和阶乘逆元：

f[0] = uf[0] = 1;
for (int i = 1; i < N; i ++ )
{
    f[i] = (LL)f[i - 1] * i % mod;
    uf[i] = (LL)uf[i - 1] * qpow(i, mod - 2, mod) % mod;
}

同样的，如果输出排列、组合结果的话需要利用公式。

时间复杂度： $O(n \log n)$

可以处理 $10^5$ 以内规模的数据

思考：读者也可以尝试写 $O(n)$ 预处理阶乘逆元。

算法4：Lucas 定理

思路

由 Lucas 定理可得：当 $p$ 为质数时，

$\large{C_a^b=C_{\frac{a}{p}}^{\frac{b}{p}} \times C_{a \bmod p}^{b \bmod p}}$

因此，我们可以写一个递归函数 LL lucas(int a, int b),递归出口是 $a_k<p, b_k<p$ 。

递归的过程相当于自上向下将 $C_{a_1}^{b_1},C_{a_2}^{b_2},…,C_{a_k}^{b_k}$ 添加到乘式里。

LL lucas(LL a, LL b)
{
    if (a < p && b < p) return C(a, b);
    return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}

这里面的 C(a, b) 是指 算法3 ，即用阶乘和阶乘逆元求组合数。

LL qpow(LL a, LL b, LL p)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return res;
}

LL C(LL a, LL b)
{
    LL res = 1;
    for (int i = 1, j = a; i <= b; i ++ , j -- )
    {
        res = (LL)res * j % p;
        res = (LL) res * qpow(i, p - 2, p) % p;
    }
    return res;
}