历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 885. 算法基础——组合数汇总小结原题链接中等

作者：

Pigwantofly , 2023-10-21 02:49:33 , 所有人可见 , 阅读 108

1

1

组合数汇总小结

一、快速幂求a^b mod p

快速幂是一种快速计算一个数的整数次幂的算法，它的核心原理是将指数进行二进制分解，利用指数的二进制位来进行幂的计算，从而减少乘法运算的次数，提高计算效率。

具体实现方法如下：

1.将指数 $n$ 转换为二进制数 $b_k,b_{k-1},…,b_1,b_0$ 。

2.用 $a$ 表示底数，计算 $a^1,a^2,a^4,…,a^{2^{k-1}},a^{2^k}$ ，并将结果保存起来。

3.对于二进制数 $b_k,b_{k-1},…,b_1,b_0$ ，从高到低依次处理每一位，如果当前位为 $1$ ，则将对应的幂累乘到结果中，最终得到 $a^n$ 。

由于幂的计算时间复杂度为 $O(\log n)$ ，因此快速幂的时间复杂度为 $O(\log n)$ ，相较于直接计算幂的时间复杂度 $O(n)$ ，快速幂算法具有更高的效率。快速幂是一种快速计算一个数的整数次幂的算法，它的核心原理是将指数进行二进制分解，利用指数的二进制位来进行幂的计算，从而减少乘法运算的次数，提高计算效率。

具体实现方法如下：

1.将指数 $n$ 转换为二进制数 $b_k,b_{k-1},…,b_1,b_0$ 。

2.用 $a$ 表示底数，计算 $a^1,a^2,a^4,…,a^{2^{k-1}},a^{2^k}$ ，并将结果保存起来。

3.对于二进制数 $b_k,b_{k-1},…,b_1,b_0$ ，从高到低依次处理每一位，如果当前位为 $1$ ，则将对应的幂累乘到结果中，最终得到 $a^n$ 。

由于幂的计算时间复杂度为 $O(\log n)$ ，因此快速幂的时间复杂度为 $O(\log n)$ ，相较于直接计算幂的时间复杂度 $O(n)$ ，快速幂算法具有更高的效率。

快速幂模板如下：

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

    return res;
}

二、快速幂求逆元（mod值为质数）

快速幂求逆元是一种常用的算法，用于计算一个数的模意义下的乘法逆元。
屏幕截图 2023-10-14 150853.png
快速幂求逆元的推导，摘自Acwing,作者ZeroAC-------->快速幂求逆元

屏幕截图 2023-10-14 151541.png

以下是使用快速幂求逆元的算法步骤：

以下是一个C++示例代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 10010;

int qmi(int a, int b, int c)
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = (LL)res * a % c;
        a = a * (LL)a % c;
        b >>= 1;
    }

    return res;
}

int main()
{
    int n;
    cin >> n;

    while(n --)
    {
        int a, p;
        cin >> a >> p;
        if(a % p) cout << qmi(a, p-2, p) << endl;
        else cout << "impossible" << endl;
    }

    return 0;
}

三、求组合数一（数据较少,对1e9+7取模）

题目描述：
组合数1
题目分析：
由题可知，一共两千个数据，数据的范围十分的小，这时我们可以使用递推法,由组合数性质公式：
$C_a^b = C_{a - 1}^{b - 1} + C_{a - 1}^{b}$
我们可以地递推出前两千项所有的组合数，时间复杂度为：O( $n^2$ ).
代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2010, mod = 1e9 + 7;
int f[N][N];

int main()
{
    //递推，f[][]代表组合数答案
    for(int i = 0; i < N; i ++)
    {
        for(int j = 0; j <= i; j ++)
        {
            if(!j) f[i][j] = 1;
            else f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % mod;
        }
    }

    int m;
    cin >> m;
    while(m --)
    {
        int a, b;
        cin >> a >> b;

        cout << f[a][b]<< endl;
    }
}

四、求组合数二（数据范围较大，对1e9+7取模）

题目描述
组合数2
题目分析：
这道题相比上一道题将数据范围增加了两百多倍，这是再使用递归处理这道题会出现空间超限的情况。这是我们需要使用组合数的另一个公式，
$C_a^b = \frac{a!}{b! (a - b)!}$
我们可以计算出b!以及另外两项的值，但我们知道，计算除法时会出现小数的情况，这种情况是很难避免的，有没有一种方法，可以让我们避免小数的运算，而是用乘法来替代他呢？

我们可以使用逆元来代替除法，我们可以使用快速幂预处理出一个阶乘数组和一个阶乘逆元数组（注意数组元素需取模），以此来解决这个组合数的计算。
代码如下：

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010, mod = 1e9 + 7;

typedef long long LL; //long long 缩写

int fact[N], infact[N];

int qmi(int a, int b) //快速幂模板
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        b >>= 1;
    }

    return res;
}
int main()
{
    fact[0] = infact[0] = 1; //初始阶乘为一

    for(int i = 1; i < N; i ++) //阶乘和逆元预处理
    {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2) % mod;
    }

    int n;
    cin >> n;

    while(n --)
    {
        int a, b;
        cin >> a >> b;

        cout << (LL)fact[a] * infact[b] % mod * infact[a - b] % mod << endl; //组合数公式
    }

    return 0;
}

五、求组合数三（数据范围超大，但取模值较小且为质数）

题目描述：
组合数3
题目分析：
这道题与上一道题相比，数据范围是超级无敌大，但与之相反的是，取模运算的值变得非常的小。我们对于这种数据范围大，但是取模数值小的组合数计算，有卢卡斯定理（Lucas）
$C_a^b = C_{\frac{a}{p}}^{\frac{b}{p}}(Lucas) * C_{a mod p}^{b mod p}$
lucas定理，摘自Acwing,作者仅存老实人 -------->Lucas证明

这样我们可以通过这个公式将一个数据范围非常大的组合数转化成一个可以计算的组合数。

代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int qmi(int a, int k, int p) //快速幂模板
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }

    return res;
}

int C(int a, int b, int p) //求Cab的方法，和定义法一样，只是进行了变形
{
    if (b > a) return 0;

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

int lucas(LL a, LL b, LL p)
{
    if(a < p && b < p) return C(a, b, p); //如果a,b比模数小，直接返回最终结果
    return (LL)C(a % p, b % p, p) * lucas(a / p , b / p, p) % p; //否则进行lucas转换,存在递归，因为不知道a/p是否比模数小
}

int main()
{
    int m;
    cin >> m;

    while (m --)
    {
        LL a, b, p;
        cin >> a >> b >> p;

        cout << lucas(a, b, p) << endl;
    }

    return 0;
}

六、求组合数四（数据范围适中，无模数，需要高精度）

题目描述：
组合数4
题目分析：
由题可知，一共五千个数据，数据的范围适中，但这道题没有取模运算，对于较大的数据需要使用高精度进行计算，由于我们这章是一个对组合数数学知识的汇总，所以对高精度不做过多赘述，这里放一个高精度乘法的代码，这里只针对C和C++,毕竟其他语言大多有打包好的高精度类或高精度语法，代码如下：

//高精度乘法
vector<int> mul(vector<int> &A, int b){
    vector<int> C;
    int t = 0;
    for(int i = 0; i < A.size(); i ++){
        t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    if(t) C.push_back(t);

    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

我们在这里是用分解质因数的方法来计算组合数的值的。首先，通过线性筛法求出 1到 a之间的所有质数，并记录下来。然后，对于每个质数p，通过函数get计算出a!中p的次数、(a−b)！中p的次数、b!中p的次数，然后相减得到p的次数，存储在数组sum中。最后，将所有质数的次数相乘，得到组合数的值。其中，函数mul是用来实现高精度乘法的。