同余方程

$a \equiv b (\mod c)$ -> $(a – b) = t \cdot c$

扩展欧几里得求逆元

费马小定理求逆元

快速幂

ll fastPow(ll a, ll b) {
    ll ret = 1;
    while(b) {
        if(b & 1) ret = ret * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ret;
}

P3811 【模板】模意义下的乘法逆元 – 洛谷

组合数学

求组合数

U51417 【模板】求组合数 – 洛谷

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 3e7 + 5;
ll Tex, jc[MAXN], inv_jc[MAXN], n, MOD;

void exgcd(ll a, ll b, ll &x, ll &y) {
    if(b == 0) {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, x, y);
    ll tmp = x;
    x = y;
    y = tmp - (a / b) * x;
}

ll fastPow(ll a, ll b) {
    ll ret = 1;
    while(b) {
        if(b & 1) ret = ret * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ret;
}

void AC() {
    ll m, n;
    cin >> m >> n;
    cout << jc[m] * inv_jc[n] % MOD * inv_jc[m - n] % MOD << "\n";
}

int main() {
    MOD = 1e9 + 7;
    n = MAXN - 5;
    jc[0] = inv_jc[0] = 1;
    for(int i = 1; i <= n; i ++) {
        jc[i] = jc[i - 1] * i % MOD;
    }
    inv_jc[n] = fastPow(jc[n], MOD - 2);
    for(int i = n - 1; i >= 1; i --) {
        inv_jc[i] = inv_jc[i + 1] * (i + 1) % MOD;
    }
    cin >> Tex;
    while(Tex --) AC();
    return 0;
}

线性代数

矩阵快速幂