Chapter 4 数学知识

知识

模板

1. 质数

(1) 质数的判定 - 试除法

#include <iostream>
#include <algorithm>

using namespace std;

bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++)
        if (x % i == 0)
            return false;
    return true;
}

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

    while (n -- )
    {
        int x;
        cin >> x;
        if (is_prime(x)) puts("Yes");
        else puts("No");
    }

    return 0;
}

(2) 分解质因数 - 试除法

[!tip] 算术基本定理 \(n=p_1^{a_1} * p_2^{a_2} * p_3^{a_3} ... p_n^{a_n}\)

#include <iostream>
#include <algorithm>

using namespace std;

void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0) // i 是 x 的 因数
        {
            // i: 底数 || s: 指数
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        divide(x);
    }

    return 0;
}

(3) 筛质数

给定一个正整数 \(n\), 请你求出 \(1\) ∼ \(n\) 中质数的个数

埃氏筛核心思想: 一个合数 必可以被一个 比它小的质数 整除

#include <iostream>
#include <algorithm>

using namespace std;

const int N= 1000010;

int primes[N], cnt; // primes[]: 记录得到的素数
bool st[N];         // st[i]: i为质数则为false否则为true

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        // 如果 st[i] 为 true，说明 i 已经被标记为合数了，直接跳过
        if (st[i]) continue;

        // i 没有被任何比它小的数筛掉，所以 i 是一个质数
        primes[cnt ++ ] = i;

        // 既然 i 是一个质数，那么 i 的所有倍数都是合数
        // 我们在这里把它们全部“划掉” (标记为 true)
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

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

    get_primes(n);

    cout << cnt << endl;
    return 0;
}

线性筛核心思想: 让每一个合数都只被它的最小质因子筛选一次

#include <iostream>
#include <algorithm>

using namespace std;

const int N= 1000010;

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

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        // 如果 st[i] 是 false，说明 i 没有被筛过，因此 i 是一个质数
        if (!st[i]) primes[cnt ++ ] = i;

        /*
        这是与埃氏筛最大的不同:

        这里的循环不是去标记i的倍数，而是用 当前数i 与 已经找到的质数primes[j] 相乘
        来筛选出新的合数
        */
        for (int j = 0; primes[j] <= n / i; j ++)
        {
            st[primes[j] * i] = true;

            // 核心: 保证了每个合数只被其 最小质因子 筛一次
            if (i % primes[j] == 0) break;
        }
    }
}

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

    get_primes(n);

    cout << cnt << endl;
    return 0;
}

2. 约数

(1) 试除法求约数

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> get_divisors(int x)
{
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}

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

    while (n -- )
    {
        int x;
        cin >> x;
        auto res = get_divisors(x);

        for (auto x : res) cout << x << ' ';
        cout << endl;
    }

    return 0;
}

(2) 约数个数 && 约数之和

// [约数个数]
// 给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 1e9+7 取模

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

const int mod = 1e9+7;

int main()
{
    int T; 
    cin >> T;
    unordered_map<int, int> h;
    while (T--)
    {
        int n; 
        cin >> n;

        // 依次求出指数
        for(int i = 2; i <= n / i; i++)
        {
            while(n % i == 0) // 底数i已锁定
            {
                // 指数++
                h[i] ++;
                n = n / i;
            }
        }
        // 如果有剩余，也是一个质因子
        if(n > 1) h[n]++;
    }

    // "约数个数"公式
    // (a1 + 1)(a2 + 1)(a3 + 1)...(an + 1)
    long long  res = 1;
    for (auto iter : h)
    {
        // res = (x1+1)(x2+1)(x3+1)…(xk+1)
        res = res * (iter.second + 1) % mod;
    }
    cout << res;
}

// [约数之和]
// 给定 n 个正整数 ai，请你输出这些数的乘积的约数之和，答案对 1e9+7 取模

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;

typedef long long LL;

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

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

    // 质因子为key，幂次为value
    unordered_map<int, int> primes; // {底数, 幂次数}

    // 对T个数分解质因子
    while (T -- )
    {
        int n;
        cin >> n;

        for (int i = 2; i <= n / i; i ++ )
        {
            while (n % i == 0) // 底数i已锁定
            {
                // 指数++
                primes[i] ++;
                n /= i;
            }
        }

        // 如果有剩余，也是一个质因子
        if (n > 1)
            primes[n] ++ ;
    }

    // "约数之和"公式
    // ( p1^0 + p1^1 + p1^2 + ... + p1^(a1) ) *
    // ( p2^0 + p2^1 + p2^2 + ... + p2^(a2) ) *
    // ...
    LL res = 1;
    for (auto p : primes)
    {   
        // 取出质因子 a=pi 和 对应的幂次 b=ai
        LL a = p.first, b = p.second;

        LL t = 1;
        while (b -- )
            t = (t * a + 1) % mod;
        // 乘入结果
        res = res * t % mod;
    }

    /*
    本质: 秦九韶算法 操作
    while (b -- )
        t = (t * a + 1) % mod;
    见下面的附录分析
    */

    cout << res << endl;

    return 0;
}

分析:

循环开始前:
    t 的初始值: t = 1
    代表的数学意义: a^0

第一次循环 (b 从 3 变为 2):
    计算过程: t = t * a + 1
             t = 1 * a + 1 = a + 1
    代表的数学意义: a^1 + a^0

第二次循环 (b 从 2 变为 1):
    计算过程: t = t * a + 1
             t = (a + 1) * a + 1 = a^2 + a + 1
    代表的数学意义: a^2 + a^1 + a^0

第三次循环 (b 从 1 变为 0):
    计算过程: t = t * a + 1
             t = (a^2 + a + 1) * a + 1 = a^3 + a^2 + a + 1
    代表的数学意义: a^3 + a^2 + a^1 + a^0

循环结束:
    b 的值变为 0，循环条件 (while b--) 不再满足，退出循环。
    最终 t 的值即为所求的和。

(3) 最大公约数

// 辗转相除法 - 最大公因数 gcd

#include <iostream>
#include <algorithm>

using namespace std;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int a, b;
        cin >> a >> b;
        cout << gcd(a, b) << endl;
    }

    return 0;
}

3. 欧拉函数

(1) 求一个数的欧拉函数

#include <iostream>
using namespace std;

int phi(int x)
{
    int res = x;

    for (int i = 2; i <= x / i; i ++)
    {
        if (x % i == 0) // 底数 pi 已锁定
        {
            res = res / i * (i - 1); // 答案, 务必先除再乘
            while (x % i == 0) x /= i;
        }
    }

    // 如果有剩余，也是一个质因子
    if (x > 1) res = res / x * (x - 1);

    return res;
}

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

    while (n -- )
    {
        int x;
        cin >> x;
        cout << phi(x) << endl;
    }
    return 0;
}

(2) 求欧拉函数之和 (筛法)

给定一个正整数 \(n\)，求 \(1\) ∼ \(n\) 中每个数的欧拉函数之和

线性筛 + 求欧拉函数

#include <iostream>
using namespace std;

typedef long long LL;

const int N = 1000010;

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

/*
1. 质数i的欧拉函数phi[i] = i - 1. 1 ~ i−1均与i互质, 共i−1个
2. phi[primes[j] * i] 分为两种情况
    - i % primes[j] == 0时：primes[j]是i的最小质因子，也是primes[j] * i的最小质因子，因此1 - 1 / primes[j]这一项在phi[i]中计算过了，只需将基数N修正为primes[j]倍，最终结果为phi[i] * primes[j].
    - i % primes[j] != 0：primes[j]不是i的质因子，只是primes[j] * i的最小质因子，因此不仅需要将基数N修正为primes[j]倍，还需要补上1 - 1 / primes[j]这一项，因此最终结果phi[i] * (primes[j] - 1).
*/

void get_eulers(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}

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

    get_eulers(n);

    LL res = 0;
    for (int i = 1; i <= n; i ++ ) res += euler[i];

    cout << res << endl;
    return 0;
}

4. 快速幂

(1) 直接求快速幂

给定 \(n\) 组 \(a_i, b_i, p_i\): 对于每组数据, 求出 \(a_i^{b_i} mod {p_i}\) 的值

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;

LL qmi(int a, int b, int p) // a^b mod p
{
    LL res = 1 % p; // 1 % p 是为了处理 p=1 的特殊情况
    while(b)
    {
        // 如果最后一位是 1，说明我们最终的结果需要乘上当前这个 a 的幂次
        if (b & 1) res = res * a % p;

        // 倍增: 
        // 无论b的当前末位是0还是1, a都要平方
        // 从 a^(2^k) 变为 a^(2^(k+1))
        a = a * (LL)a % p;

        // 已经处理完了 b 的最后一位，现在把它“扔掉”
        b >>= 1;
    }
    return res;
}


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

    while (n --)
    {
        int a, b, p;
        cin >> a >> b >> p;
        cout << qmi(a, b, p) <<endl;
    }
    return 0;
}

(2) 快速幂求乘法逆元

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;

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

/*
1. 当 p 与 n 互质时: n 存在乘法逆元

2. 当 p 是质数时: (n)^(p-2) 就是 n 的乘法逆元

   (n)^(-1) mod p == (n)^(p-2) mod p
*/

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

    while(n -- )
    {
        int a, p;
        cin >> a >> p;
        if (a % p == 0) {
            // b 存在乘法逆元的充要条件是 b 与模数 m 互质
            puts("impossible");
        }
        else {
            // 当模数 m 为质数时, b^(m−2) 即为 b 的乘法逆元
            cout << qmi(a, p - 2, p) << endl;
        }
    }
    return 0;
}

5. 扩展欧几里得算法

扩展欧几里得问题:

给定 n 对正整数 ai, bi. 对于每对数, 求出一组 xi , yi, 使其满足: ai × xi + bi × yi = gcd(ai,bi).

#include<bits/stdc++.h>
using namespace std;

int exgcd(int a, int b, int &x, int &y)
{
    // 返回 gcd(a,b) 并求出解 (引用带回)
    if (b==0) {
        x = 1, y = 0;
        return a;
    }

    // 纯数学推导, 记模板即可
    int x1, y1, gcd;

    gcd = exgcd(b, a%b, x1, y1);
    x = y1, y = x1 - a / b * y1;

    return gcd; 
}

int main()
{
    int n, a, b, x, y;
    cin >> n;

    while(n--)
    {
        cin >> a >> b;
        exgcd(a, b, x, y);
        cout << x << " " << y <<endl;
    }
    return 0;
}

线性同余方程:

给定 \(n\) 组数据 ai, bi, mi. 对于每组数求出一个 xi，使其满足 ai × xi ≡ bi (mod mi). 如果无解, 则输出 impossible.

#include<bits/stdc++.h>
using namespace std;
int n, x, y;
typedef long long LL;

int exgcd(int a, int b, int &x, int &y)
{
    // 返回 gcd(a,b) 并求出解 (引用带回)
    if (!b) {
        x = 1, y = 0;
        return a;
    }

    int d = exgcd(b, a % b, x, y);
    int z = x;
    x = y;
    y = z - a / b * y;

    return d;
}

int main()
{
    cin >> n;

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

        int d = exgcd(a, m, x, y);

        if (b % d) puts("impossible");
        else {
            x = (LL) x * b / d % m;
            cout << x << endl;
        }
    }
    return 0;
}

[!tip] alias type 格式: typedef existing_type new_alias 例如: typedef long long LL

6. 中国剩余定理

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;

LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }

    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;

    return d;
}


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

    LL x = 0, m1, a1;
    cin >> m1 >> a1;

    for (int i = 0; i < n - 1; i++)
    {
        LL m2, a2;
        cin >> m2 >> a2;
        LL k1, k2;
        LL d = exgcd(m1, m2, k1, k2);

        if ((a2 - a1) % d) {
            x = -1;
            break;
        }

        k1 *= (a2 - a1) / d;
        k1 = (k1 % (m2/d) + m2/d) % (m2/d);

        x = k1 * m1 + a1;

        LL m = abs(m1 / d * m2);
        a1 = k1 * m1 + a1;
        m1 = m;
    }

    if (x != -1) x = (a1 % m1 + m1) % m1;

    cout << x << endl;
    return 0;
}

7. 高斯消元

通用步骤:

1. 高斯消元得到上三角矩阵
   1. 枚举列
   2. 找到当前列的非零行, 选择 "绝对值最大的" 作为 "candidate line"
   3. "candidate line" 换到 剩余行 的最上面
   4. 剩余行中除去最上面一行，下面所有行的当前列都消零
2. 判断解的种类
   1. 无解: finally. r < n && exist(0 == N)
   2. 无穷多解: finally. r < n && exist(0 == 0)
   3. 唯一解: finally. r == n

#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

const int N = 110;
const double egs = 1e-6; // 浮点数判0

double a[N][N];
int n;

int gauss()
{
    int r, c;
    // c 从 0 遍历到 n-1 (所有变量列)
    // r 记录已经有多少个主元行，也代表当前待处理的行号

    for (r = 0, c = 0; c < n; c++) 
    {
        // 1. 找主元 (所有"没考察"行中该列绝对值max的)
        int t = r;
        for (int i = r + 1; i < n; i++) // 已做到r, 从r+1开始做
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;

        // 如果当前列从r行往下都是0，则处理下一列，r保持不变
        if (fabs(a[t][c]) < egs) continue;

        // 2. 将 第 r 行 "置顶"
        for (int i = c; i <= n; i++) swap(a[t][i], a[r][i]);

        // 3. 将主元行的主元系数变为 1
        // 为了避免在循环中修改除数 a[r][c]，先将其存起来
        double pivot = a[r][c];
        for (int i = c; i <= n; i++) a[r][i] /= pivot;

        // 4. 用主元行消去下面各行的第 c 列
        for (int i = 0; i < n; i++) {
            if (i != r) { // 对除了r行以外的所有行进行操作
                double factor = a[i][c];
                for (int j = c; j <= n; j++) {
                    a[i][j] -= factor * a[r][j];
                }
            }
        }

        // 成功处理了一行，r增加
        r++;
    }

    // --- 后续判断逻辑 ---

    // 如果有效方程数 r 小于变量数 n
    if (r < n) 
    {
        for (int i = r; i < n; i++)
        {
            // 出现了 0 = 非零 的情况，无解
            if (fabs(a[i][n]) > egs) 
                return 2;
        }
        // 出现了 0 = 0 的情况，有无穷多解
        return 1;
    }

    // r == n，有唯一解
    // 此时已经是一个对角矩阵（简化阶梯型），a[i][n] 就是解
    return 0;
}

int main()
{
    cin >> n;
    for(int i=0;i<n;i++)
        for(int j=0;j<=n;j++)
            cin >> a[i][j];

    int t = gauss();

    if (t==0) { // 固定输出的小数数位
        for (int i=0; i<n; i++) cout << fixed << setprecision(2) << a[i][n] << endl;
    }
    else if (t==1) puts("Infinite group solutions");
    else puts("No solution");

    return 0;
}

#include <iostream>
using namespace std;

const int N = 110;
int a[N][N];
int n;

int gauss()
{
    int r, c;

    for (r = 0, c = 0; c < n; c++) 
    {
        // 1. 找主元 (所有"没考察"行中该列绝对值max的)
        int t = r;
        for (int i = r; i < n; i++)
            if (a[i][c]) {
                t = i;
                break;
            }

        // 如果当前列从r行往下都是0，则处理下一列，r保持不变
        if (a[t][c] == 0) continue;

        // 2. 将 第 r 行 "置顶"
        for (int i = c; i <= n; i++) swap(a[r][i], a[t][i]);

        // 3. 用主元行消去下面各行的第 c 列
        //    其实就是进行 XOR 操作
        for (int i = r + 1; i < n; i++) 
        {
            if (a[i][c])
                for (int j = c; j <= n; j++)
                    a[i][j] ^= a[r][j];
        }

        r++;
    }

    // --- 后续判断逻辑 ---

    if (r < n) {
        for (int i = r; i < n; i++)
            if (a[i][n])
                return 2;
        return 1;
    } 
    else {
        for (int i = n - 1; i >= 0; i--) 
        {
            for (int j = i + 1; j < n; j++) 
            {
                a[i][n] ^= a[i][j] * a[j][n];
            }
        }
    }

    return 0;
}

int main()
{
    cin >> n;

    for (int i = 0; i < n; i++)
        for (int j = 0; j <= n; j++)
            cin >> a[i][j];

    int res = gauss();

    if (res == 0) 
        for (int i = 0; i < n; i++) cout << a[i][n] <<endl;
    else if (res == 1) 
        cout << "Multiple sets of solutions" <<endl;
    else 
        cout << "No solution" <<endl;

    return 0;
}

8. 组合数

给定 n 组询问，每组询问给定两个整数 a, b. 请你输出 \(C_b^a\) mod(1e9+7) 的值

根据不同的数据范围选择不同的做法, 下面的方法自low向fancy

(1) 利用数学公式: C[a][b] = C[a-1][b-1] + C[a-1][b]

#include <iostream>
#include <algorithm>
using namespace std;

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

int c[N][N];

void init()
{
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j <= i; j ++ )
            if (j == 0) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}

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

    init();

    while (n --) {
        int a, b;
        cin >> a >> b;
        cout << c[a][b] << endl;
    }

    return 0;
}

(2) 利用定义 + 乘法逆元

个人认为这个方法最为主流

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;

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

int fact[N], infact[N];

/*
fact[i]   = i!        mod 1e9+7
infact[i] = (i!)^(-1) mod 1e9+7
*/

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


int main()
{
    // 初始化
    fact[0] = infact[0] = 1;

    // 预处理
    for (int i = 1; i < N; i ++ )
    {
        // fact[]: 阶乘的定义
        fact[i] = (LL)fact[i - 1] * i % mod;

        // infact[]: 乘法逆元
        // if b 与 m 互质, b 的乘法逆元是 b^(m-2)
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % 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) 卢卡斯定理

#include <iostream>
#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)
{
    if (b > a) return 0;

    int res = 1;
    for (int i = 1, j = a; i <= b; i ++, j -- )
    {
        // a!/(b!(a-b)!) = (a-b+1)*...*a / b! 分子有b项
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2, p) % p;
    }
    return res;
}

int lucas(LL a, LL b, int p)
{
    if (a < p && b < p) return C(a, b, p);

    // a%p后肯定是<p的. 所以可以用C()
    // 但a/p后不一定<p. 所以用lucas继续递归
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

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

    while (n -- )
    {
        LL a, b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }

    return 0;
}

(4) 变态: 高精度 + 求组合数 (不管了, 直接复制模板, 考了认栽...)

#include<iostream>
#include<algorithm>
#include<vector>

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]*i<=n;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0)break;//==0每次漏
        }
    }
}
// 对p的各个<=a的次数算整除下取整倍数
int get(int n,int p)
{
    int res =0;
    while(n)
    {
        res+=n/p;
        n/=p;
    }
    return res;
}
//高精度乘
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;
    }
    // while(C.size()>1 && C.back()==0) C.pop_back();//考虑b==0时才有pop多余的0 b!=0不需要这行
    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(a,p)-get(a-b,p)-get(b,p);//是a-b不是b-a
    }

    vector<int> res;
    res.push_back(1);

    for (int i = 0; i < cnt; i ++ )
        for (int j = 0; j < sum[i]; j ++ )//primes[i]的次数
            res = mul(res, primes[i]);

    for (int i = res.size() - 1; i >= 0; i -- ) printf("%d", res[i]);
    puts("");

    return 0;
}

(5) 卡特兰数的应用

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

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

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

int n;
int fact[N], infact[N];

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

void init() {
    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;
    }
}

/*
1. 当 p 与 n 互质时: n 存在乘法逆元

2. 当 p 是质数时: (n)^(p-2) 就是 n 的乘法逆元

   (n)^(-1) mod p == (n)^(p-2) mod p
*/

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

    int res_part1 = (LL) fact[2 * n] * infact[n] % mod * infact[n] % mod; // c[2n][n]
    int res_part2 = (LL) qmi(n + 1, mod - 2) % mod; // (n+1)^(-1) mod p
    cout << (LL) res_part1 * res_part2 % mod << endl;
    return 0;
}

以下这些问题的答案都是catalan数: