排列组合

---

一些关于排列组合的公式

一般求排列 $\binom{n}{m}$

(1) $C_b^a=C_{b−1}^{a−1}+C_b^{a−1}$

根据组合递推式，可以预处理模数固定且处理的$a,b$较小的组合式的递推式

const int N = 2010, mod = 1e9 + 7; //一般也开不了太大,模数根据题意另取
ll f[N][N];
//预处理
void init() {
    for(int i = 0; i < N; i++) {
        for(int j = 0; j <= i && j < N; j++) {
            if(!j) f[i][j] = 1;
            else f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % mod;
        }
    }
}

（2）$C_b^a = \frac{a!}{b!\times (a-b)!}$

利用快速幂求逆元，结合数组可以预处理出除数，加快速度，预处理做法只在模数固定下才可以使用

const int N = 100010, mod = 1e9 + 7;
ll qmi(ll a, ll k, ll mod) {
    ll ans = 1;
    while(k) {
        if(k & 1) ans = ans * a % mod;
        a = a * a  % mod;
        k >>= 1;
    }
    return ans;
}
ll q[N], ivq[N];
void init() {
     ivq[0] = q[0] = 1;
    for(int i = 1; i < N; i++) {
        q[i] = q[i - 1] * i % mod;
        ivq[i - 1] = qmi(q[i], mod - 2, mod);
    }
}
//之后求答案C a,b 时，就是 q[a] * ivq[b] % mod * ivq[a - b] % mod;

(3) $lucas$ 定理，在求 $C_b^a\ mod\ p$ 时，如果 $a,b$ 数值太大，可以使用卢卡斯定理压缩时间复杂度

ll qmi(ll a, ll k, ll mod) {
    ll ans = 1;
    while(k) {
        if(k & 1) ans = ans * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return ans;
}
//线性求逆元，时间复杂度On
ll C(ll a, ll b, ll mod) {
    ll ans = 1;
    for(ll i = a, j = 1; j <= b; j++, i--) {
        ans  = ans * i % mod;
        ans = ans * qmi(j, mod - 2, mod) % mod;
    }
    return ans;
}
//卢卡斯定理，可以压缩时间复杂度到类似O(mod * log(min(a, b)))
ll lucas(ll n, ll k, ll mod) {
    if(n < mod && k < mod)
        return C(n, k, mod);
    return C(n % mod, k % mod, mod) * lucas(n / mod, k / mod, mod) % mod;
}

(4)高精度求组合数

#include <bits/stdc++.h>

using namespace std;

/*
大概思路就是分解上下的质因数个数，之后用高精度乘法解决
*/

const int N = 5010;

int primes[N], cnt;
int sum[N];
bool st[N];


//求质数的量
void get_primes(int n) {
    
    for(int i = 2; i <= n; i++) {
        if(!st[i]) {
            primes[cnt++] = i;
        }
        for(int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

//求某一个阶乘里面的质数p的数量
int get_prime_num(int n, int p) {
    int ans = 0;
    while(n) {
        ans += n / p;
        n /= p;
    }
    return ans;
}

//高精度乘法
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;
    }
    while(t) {
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

int main() {
    
    int a, b;
    cin >> a >> b;
    get_primes(a);
    for(int i = 0; i < cnt; i++) {
        int p = primes[i];
        sum[i] = get_prime_num(a, p) - get_prime_num(b, p) - get_prime_num(a - b, p); 
    }
    
    vector<int>f;
    f.push_back(1);
    
    for(int i = 0; i < cnt; i++) {
        for(int j = 0; j < sum[i]; j++) {
            f = mul(f, primes[i]);
        }
    }
    for(int i = f.size() - 1; ~i; i--) {
        cout << f[i];
    }
    cout << '\n';
    return 0;
}

题目：https://www.acwing.com/problem/content/890/

(5)卡特兰数

https://www.acwing.com/problem/content/891/

给定 $n$ 个 $0$ 和 $n$ 个 $1$，它们将按照某种顺序排成长度为 $2n$ 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 $0$ 的个数都不少于 $1$ 的个数的序列有多少个。

输出的答案对 $10^9+7$ 取模。

卡特兰数是排列组合里较长出现的配合容斥的算法，通过将目标转化为图的形式求解全解与非法解，容斥后为正确答案

#include <iostream>

using namespace std;
typedef long long LL;
const int N = 100010, mod = 1e9 + 7;
int n;

int qmi(LL a, int k) {
    LL ans = 1;
    while(k) {
        if(k & 1) ans = ans * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return ans;
}

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

int main() {
    cin >> n;
    int a = C(n * 2, n), b = C(n * 2, n - 1);
    
    cout << ((a - b) % mod + mod) % mod << endl;
    
}