快速幂

int qpow(int x, int y, int m) {
    int ans = 1 % m;
    while (y) {
        if (y & 1)ans = ans * x % m;
        x = x * x % m;
        y >>= 1;
    }
    return ans;
}

矩阵快速幂

struct matrix {
    int n, m;
    vector<vector<int>> a;

    matrix(int n, int m, vector<vector<int>> a = {}) : n(n), m(m), a(n, vector(m, 0)) {
        if (!a.empty())copy(a.begin(), a.end(), this->a.begin());
    }

    matrix operator*(matrix &b) {
        matrix c(n, b.m);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < b.m; ++j) {
                for (int k = 0; k < m; ++k) {
                    c.a[i][j] = c.a[i][j] + a[i][k] * b.a[k][j] % MOD;
                }
            }
        }
    }

    matrix operator^(int k) {
        //快速幂
        matrix c(n, m);

        //单位阵
        for (int i = 0; i < n; ++i) {
            c.a[i][i] = 1;
        }

        //复制一个自身
        matrix x = *this;

        while (k) {
            if (k & 1)c = c * x;
            x = x * x;
            k >>= 1;
        }
        return c;
    }
};

完整的矩阵结构体

struct matrix {
    lld n, m;
    vector<vl > a;

    matrix(lld n, lld m, vector<vl > a = {}) : n(n), m(m), a(n, vl(m, 0)) {
        if (!a.empty())copy(a.begin(), a.end(), this->a.begin());
    }

    matrix operator*(matrix &b) {
        matrix c(n, b.m);
        for (lld i = 0; i < n; ++i) {
            for (lld j = 0; j < b.m; ++j) {
                for (lld k = 0; k < m; ++k) {
                    c.a[i][j] = c.a[i][j] + a[i][k] * b.a[k][j] % MOD;
                }
            }
        }
        return c;
    }

    matrix operator+(matrix &b) {
        matrix c(n, m);
        for (lld i = 0; i < n; ++i) {
            for (lld j = 0; j < m; ++j) {
                c.a[i][j] = a[i][j] + b.a[i][j];
            }
        }
        return c;
    }

    matrix operator-(matrix &b) {
        matrix c(n, m);
        for (lld i = 0; i < n; i++) {
            for (lld j = 0; j < m; j++) {
                c.a[i][j] = a[i][j] - b.a[i][j];
            }
        }
        return c;
    }

    matrix operator%(lld mod) {
        matrix c(n, m);
        for (lld i = 0; i < n; i++) {
            for (lld j = 0; j < m; j++) {
                c.a[i][j] = a[i][j] % mod;
            }
        }
        return c;
    }

    matrix operator^(lld k) {
        //快速幂
        matrix c(n, m);
        for (lld i = 0; i < n; i++) {
            c.a[i][i] = 1;
        }
        matrix x = *this;
        while (k) {
            if (k & 1) {
                c = c * x;
            }
            x = x * x;
            k >>= 1;
        }
        return c;
    }

    void print() {
        //行尾无空格
        for (lld i = 0; i < n; i++) {
            for (lld j = 0; j < m; j++) {
                cout << a[i][j] << " \n"[j == m - 1];
            }
        }
    }
};

斐波拉契数列

矩阵解

$$\begin{bmatrix} F_{n+2} & F_{n+1} \\ F_{n+1} & F_{n} \end{bmatrix}= {\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}}^{n+1}$$

auto getFB(int n) {
    matrix a(2, 2, {{1, 1},{1, 0}});
    a = a ^ (n + 1);
    return a.a[1][1];
}

前n项和

$$S_n = F_{n+2}-1$$

auto sumFB(int n) {
    matrix a(2, 2, {{1, 1},{1, 0}});
    a = a ^ (n + 1);
    return a.a[0][0] - 1;
}

最大公约数，最小公倍数

$$gcd(a,b)=gcd(b,a\%b)$$

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

lld gcd_sub(lld a, lld b) {
    if (a < b)swap(a, b);
    if (b == 1)return a;
    else return gcd_sub(b, a / b);
}

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

分解质因数

$$N = p_1^{c_1}*p_2^{c_2}*…*p_k^{c_k}$$

void div(int x) {
    for (int i = 2; i <= x / i; ++i) {
        int s = 0;
        while (x % i == 0) {
            s++;
            x /= i;
        }
        if (s)cout << i << ' ' << s << endl;
    }
    if (x > 1)cout << x << ' ' << 1 << endl;
}

因数个数

$$(c_1+1)*(c_2+1)*…*(c_k+1)$$

int cntFac(int x) {
    int ans = 1;
    for (int i = 2; i <= x / i; ++i) {
        int s = 0;
        while (x % i == 0) {
            s++;
            x /= i;
        }
        if (s)ans *= (s + 1);
    }
    if (x > 1)ans *= 2;
    return ans;
}

因数之和

$$(p_1^{0}+p_1^{1}+…+p_1^{c_1})*(p_2^{0}+p_2^{1}+…+p_2^{c_2})*…*(p_k^{0}+p_k^{1}+…+p_k^{c_k})$$

n个整数的最小公倍数的因数个数

int n;
int p[100010];

void div(int x) {
    for (int i = 2; i <= x / i; ++i) {
        int s = 0;
        while (x % i == 0) {
            s++;
            x /= i;
        }
        p[i] = max(p[i], s);
    }
    p[x] = max(p[x], 1);
}

int main() {
    cin >> n;
    int t, mx = 0;
    for (int i = 0; i < n; ++i) {
        cin >> t;
        div(t);
        mx = max(mx, t);
    }
    lld sum = 1;
    for (int i = 2; i <= mx; ++i) {
        if (p[i]) sum = sum * (p[i] + 1) % 998244353;
    }
    cout << sum << endl;
    return 0;
}

欧拉函数

$1-N$中与$N$互质的数的个数被称为欧拉函数，记为$ϕ(N)$。
若在算数基本定理中，$N=p_1^{a_1}*p_2^{a_2}*…p_m^{a_m}$，则：
$ϕ(N) = N*{\frac{p_1-1}{p_1}}*{\frac{p_2-1}{p_2}}*…*{\frac{p_m-1}{p_m}}$

int ola(int x) {
    int res = x;
    for (int i = 2; i <= x / i; ++i) {
        if (x % i == 0) {
            res = res / i * (i - 1);
            while (x % i == 0)x /= i;
        }
    }
    if (x > 1)res = res / x * (x - 1);
    return res;
}

扩展欧几里得

AcWing 877. 扩展欧几里得算法
$$\begin{array}{l} 已知： \left\{\begin{matrix} xa+yb=gcd(a,b) \\ x_1a_1+y_1b_1=gcd(a_1,b_1)\\ gcd(a,b)=gcd(b,a\%b)\\ a_1=b\\ b_1=a\%b\\ \end{matrix}\right. =>xa+yb=x_1b+y_1(a\%b)\\ 提取系数：\\ xa+yb=x_1b+y_1(a\%b)\\ xa+yb=x_1b+y_1(a-{\left \lfloor \frac{a}{b} \right \rfloor}b)\\ xa+yb=x_1b+y_1a-y_1{\left \lfloor \frac{a}{b} \right \rfloor}b\\ xa+yb=y_1a+(x_1-y_1{\left \lfloor \frac{a}{b} \right \rfloor})b\\ 得：\\ \left\{\begin{matrix} x = y_1 \\ y = x_1-y_1{\left \lfloor \frac{a}{b} \right \rfloor} \end{matrix}\right. \end{array} $$

int extern_gcd(int a, int b, int &x, int &y) {
    if (b) {
        int x1, y1;
        int d = extern_gcd(b, a % b, x1, y1);
        x = y1;
        y = x1 - a / b * y1;
        return d;
    } else {
        x = 1;
        y = 0;
        return a;
    }
}

逆元

逆元 —— 广义化的倒数 - 知乎

相关定义

单位元

【定义1】在一个集合中，对于某种运算$*$（这里代表通用运算的表示符号，并不是特指乘法），如果对于任何的集合元素 $a$，和元素$e$运算，得到还是集合元素$a$本身，则称$e$为这个运算下的单位元。

例如：
加法中，$a+e=e+a=a$，单位元$e=0$
乘法中，$a*e=e*a=e$，单位元$e=1$

逆元

【定义2】在一个集合中，对于某种运算$*$，如果任意两个元素的运算结果等于单位元，则称这两个元素互为逆元。

例如：
加法中，$a$的逆元为$-a$，$-a + a = e = 0$
乘法中,$a$的逆元为$a^{-1}$，$a * a^{-1} = e = 1$

模乘的单位元

$$e(mod n)=1$$
$$a(mod\ n)*1(mod\ n)=a(mod\ n)$$

模乘的逆元

模乘运算中，任意整数$a(mod\ n)$的逆元表示为$a^{-1}mod\ n$

求法

扩展欧几里得

时间：$O(log(n))$，通用且常用

例1：给定正整数$a$和$n$，求满足等式$ax≡1(mod\ n)$的$x$的最小正整数解。如果不存在，则返回$-1$。

$$\begin{array}{l} 就是一个求逆元的题，x即为a在模n乘法上的逆元。\\ ax\equiv 1(mod\ n)\\ 转换：ax = kn+1\\ 移项：ax-kn=1\\ k为整数无论正负，令-k=k，改写为：\\ ax+kn=1\\ 发现就是扩展欧几里得：y=k，b=n，gcd(a,b)=1\\ ax+by=1 \end{array} $$
那么当$gcd(a,n)==1$的时候，解存在

void get_inv_by_gcd(lld a,lld n,lld x,lld k){
    //利用扩展欧几里得计算x的一个可行解；算出的x有正有负
    lld d = extern_gcd(a,n,x,k);
    //当gcd(a,n)==1时，才有解
    if(d!=1)cout<<"impossible"<<endl;
    //将x转化成最小的与x模n同余的正整数；
    else cout<<(x%n+n)%n<<endl;
}

快速幂-费马小定理

时间：$O(log(n))$，要求：p为质数

费马小定理：p为素数，且a与p互质，则$a^{p-1}≡1(mod\ n)$

–

例2：给定正整数$a$和素数$p$，求满足等式$ax≡1(mod\ p)$的$x$的最小正整数解。如果不存在，则返回$-1$。
与上例不同的是模数为素数

$$\begin{array}{l} 当a被p整除时，ax\equiv 0(mod\ n)，返回-1\\ 否则由费马小定理：a^{p-1}≡1(mod\ n)\\ aa^{p-2}≡1(mod\ n)\\ 得x=a^{p-2} \end{array} $$

void get_inv_by_qpow(int a, int p) {
    if (a % p == 0)cout << "impossible" << endl;
    else cout << qpow(a, p - 2, p) << endl;
}

欧拉函数

时间：$sqrt(n)$，不要求p为质数，这相当于费马小定理求逆元的扩展，先求出欧拉函数，再求逆元

void get_inv_by_ola(int a, int p) {
    if (a % p == 0)cout << "impossible" << endl;
    else cout << qpow(a, ola(p) - 1, p) << endl;
}

线性递推

略

ll inv[N];   // 逆元表

void mod_inverse(ll n, ll mod){
    inv[0] = inv[1] = 1;
    for(int i = 2; i <= n; i++)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}

线性同余方程

给定$a$,$b$,$m$，求$x$满足$ax≡b(mod\ m)$

$$\begin{array}{l} 前提定理：ax+by=gcd(a,b)\\ ax \equiv b(mod\ m)\\ ax=km+b\\ ax-km=b\\ ax+km=b\\ 当b\%gcd(a,m)==0时，有解\\ 令b/gcd(a,m)=r\\ a\frac{x}{r}+k\frac{m}{r}=gcd(a,m)\\ 使用扩展欧几里得解得一个解x’\\ x = x’r\\ x = x’(b/gcd(a,m))\\ \end{array} $$

int main() {
    int a, b, m;
    int x, y;
    cin >> a >> b >> m;
    int d = extern_gcd(a, m, x, y);
    if (b % d) {
        cout << "impossible" << endl;
    } else {
        //缩小到m以内
        cout << 1ll * x * (b / d) % m << endl;
    }
    return 0;
}

中国剩余定理

求$x$，满足$\left\{\begin{matrix} x\equiv a_1(mod\ m_1)\\ x\equiv a_2(mod\ m_2)\\ …\\ x\equiv a_n(mod\ m_n)\\ \end{matrix}\right.$

$$\begin{array}{l} 中国剩余定理：对于上述方程组，在m_1、m_2…m_n两两互质时有解；\\ 令M=m_1*m_2*…*m_n;\\ M_i=\frac{M}{m_i}，M_i^{-1}为M_i的逆元\\ 在mod\ M下，有唯一解x=(a_1M_1M_1^{-1}+a_2M_2M_2^{-1}+…a_nM_nM_n^{-1})mod\ M \end{array} $$

LL CRT(int n, LL* a, LL* m) {
  LL M = 1, ans = 0;
  for (int i = 1; i <= n; i++) M *= m[i];
  for (int i = 1; i <= n; i++) {
    LL Mi = M / m[i], x, y;
    extern_gcd(Mi, m[i], x, y);  // x * Mi mod m[i] = 1
    ans = (ans + a[i] * Mi * x % M) % M;
  }
  return (ans % M + M) % M;
}

扩展中国剩余定理

QAQ

求组合数

杨辉三角规律：每个数为它上面两个数的和

原理:$C_a^b=C_{a-1}^{b-1}+C_{a-1}^b$
范围：$1<=n<=100000，1<=b<=a<=2000$

int c[2048][2048];

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

int n;

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

预处理mod 1e9+7的阶乘及其逆元(费马小定理)

原理：$C_a^b=\frac{a!}{b!*(a-b)!}mod\ MOD=a!*inv(b!)*inv((a-b)!) $

int qpow(int x, int y, int m) {
    int ans = 1 % m;
    while (y) {
        if (y & 1)ans = 1ll * ans * x % m;
        x = 1ll * x * x % m;
        y >>= 1;
    }
    return ans;
}

int jie[100010], inv[100010];

void init() {
    jie[0] = inv[0] = 1;
    for (int i = 1; i <= 100000; ++i) {
        jie[i] = 1ll * jie[i - 1] * i % MOD;
        inv[i] = 1ll * inv[i - 1] * qpow(i, MOD - 2, MOD) % MOD;
    }
}

int main() {
    int n, a, b;
    cin >> n;
    init();
    while (n--) {
        cin >> a >> b;
        cout << 1ll * jie[a] * inv[b] % MOD * inv[a - b] % MOD << endl;
    }
    return 0;
}

卢卡斯(lucas)定理

高精度-素数组合

容斥原理

博弈论