ReMind

Recent Writing

See 247 more →

组合数

7 min read

递推求组合数

数据范围（a,b）小 2000

计算组合数的公式很简单，但是当查询次数多时，时间复杂度很高，所以采用递推的方法

取一个假定是特殊的数，有两种组合方法，一种是取了这个数的，一种是没有的 两种组合数的相加就是总体的组合数

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int N = 2010, m = 1e9 + 7;
 
int c[N][N];
int n;
 
void init()
{
    for(int i = 0 ; i < N; i ++)
    {
        for(int j = 0; j <= i; j ++)
        { 
            if(!j)   c[i][j] = 1;  // 如果取0的话，组合数结果是1
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % m;  // 否则递推，注意是从1开始算，即每一个i-1算好了再算的i，所以可以直接用公式
            // 当j=i时，c[i-1][j]是没有算过的，事实中不存在，数组中为0
        }
    }
}
 
 
int main()
{
    cin >> n;
    
    init();
    
    while(n --)
    {
        int a, b;
        
        cin >> a >> b;
        
        cout << c[a][b] << endl;  //索引不需要变化
    }
    
    return 0;
}

快速幂求组合数

数据范围大

利用组合数公式

  1. 求阶乘

  2. 由于取模的运算中 a/b 取模不等于a取模除以b取模，但是乘法可以，要转换为乘法后取模的值与原来相等，考虑逆元 使用快速幂求逆元 求逆元

  3. 用因为

    即 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
typedef long long LL;
 
const int N = 100010, m = 1e9 + 7;
 
LL f[N];
LL inf[N];
 
//m是很大的质数，任何b都比m小，即互质，所以可以用qmi求逆元
LL qmi(LL a, LL k, LL m)
{
    LL ans = 1;
    while(k)
    {
        if(k & 1) ans = ans * a  % m;
        k >>= 1;
        a = a * a % m;
    }
    
    return ans;
}
 
int main()
{
    for(int i = 0; i < N ; i ++)
    {
        if(!i)  f[i] = inf[i] = 1;
        else
        {
            f[i] = i *  f[i - 1] % m;  // 阶乘
            inf[i] = inf[i - 1] * qmi(i, m - 2, m) % m;  // 阶乘的逆元
        }
    }
    
    int n;
    cin >> n;
    
    while(n --)
    {
        LL a, b;
        cin >> a >> b;
        
        cout << f[a] * inf[a - b] % m * inf[b] % m << endl;
        
    }
    
    return 0;
}

卢卡斯定理

当数据（a，b）的值很大，同时查询次数不多

Transclude of 数学#^a783c3

  1. 当数据值很大时，递推与阶乘都没法求解，利用卢卡斯定理，可以将问题化简成合理范围
  2. 卢卡斯定理将数据取模后，范围缩小到模数p的范围，然后再利用快速幂求逆元与阶乘算组合数求解
LL qmi(LL a, int k, int p)
{
    int res = 1;
    while(k)
    {
        if(k & 1)  res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    
    return res;
}
 
 
//按定义求组合数
LL C(LL a, LL b)
{
    LL ans = 1;  // 相乘后可能爆int
    for(int i = a, j = 1; j <= b; i --, j ++)
    {
        ans = ans * i % p;
        ans = ans * qmi(j, p - 2, p) % p;
    }
    
    return ans;
}
 
LL lucas(LL a, LL b)
{
    if(a < p && b < p) return C(a, b);  //都小于p就拆不开了
    return C(a % p, b % p) * lucas(a / p, b / p) % p; // 有一个大于p还可以拆
}

注意范围很大，再计算时为了避免爆 int 使用 long long

高精度求组合数

确切求出某个组合数而且数据范围超过要求的时间复杂度

  1. 找素数
  2. 找阶乘中这个素数的倍数的个数
  3. 高精度乘法
int p[N];
bool st[N];
 
int cnt = 0;
 
//素数(线性)
void get_p(int n)
{
    
    for(int i = 2; i <= n; i ++)  // 一直到n，因为n自己可能是一个素数
    {
        if(!st[i])  p[cnt ++] = i;
        for(int j = 0; p[j] <= n / i; j ++)
        {
            st[p[j] * i] = true;
            if(i % p[j] == 0)  break;
        }
    }
}
 
//素数的个数
// 通过每次除以素数p,可以算一个数里有多少个p
int get_n(int a, int p)
{
    int ans = 0;
    
    while(a)
    {
        ans += a / p;
        a /= p;
    }
    
    return ans;
}
 
 
vector<int> mul(vector<int> &a, int p)
{
    vector<int> c;
    int t = 0;
    for(int i = 0 ; i < a.size(); i ++)
    {
        t += a[i] * p;
        c.push_back(t % 10);  // 存下当前位
        t /= 10;  // 其他数进位
    }
    
    while(t)
    {
        c.push_back(t % 10);
        t /= 10;
    }
    
    return c;
}
 
 
 
int main()
{
    int a, b;
    cin >> a >> b;
    
    vector<int> ans;
    ans.push_back(1);
    
    get_p(a);
    
    int sum[N] = {};
    for(int i = 0; i < cnt; i ++)
    {
        int pri = p[i];
        sum[i] = get_n(a, pri) - get_n(b, pri) - get_n(a - b, pri);  // 这一步是关键，将阶乘换成计算a,b中每个素数的个数，并且通过减法去掉 实际组合数计算中除法去掉的素数的数量 将过程的数值大小大幅减少
    }
    
    //算出每个素数有多少之后，高精度求组合数的阶乘和除法算完之后，素数的值乘以其数量再相乘就是组合数
    for(int i = 0; i < cnt; i ++)
    {
        int res = 1;
        for(int j = 0; j < sum[i]; j ++)
            ans = mul(ans, p[i]);
    }
    
    for(int i = ans.size() - 1; i >= 0; i --)
        cout << ans[i];  //逆序输出，因为高精度乘法是顺序的
        
    cout << endl;
    
    return 0;
}

Graph View

Backlinks