OI笔记 | 入门数学模板

更难的部分有新的文章。

乘法逆元

基础中的基础。

定义为 $ax \equiv 1 \pmod b$ 的解 $x$ 为 $a$ 模 $b$ 意义下的逆元,记作 $a^{-1}$。

快速幂

由于 $ax\equiv 1 \pmod b$;

所以 $ax\equiv a^{b - 1}\pmod b$

所以 $x\equiv a^{b - 2}\pmod b$

所以快速幂即可。

ll qpow(ll x, ll y) {
    ll ret = 1;
    for(; y; y >>= 1, (x *= x) %= MOD)
        if(y & 1)   (ret *= x) %= MOD;
    return ret;
}

Exgcd

洛谷 P5656

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

线性求逆元

inv[1] = 1;
for (int i = 2; i <= n; ++i)
    inv[i] = (p - p / i) * inv[p % i] % p;

线性求阶乘的逆元:

facinv[n] = qpow(n, p - 2);
for(int i = n - 1; i >= 0; i--)
    facinv[i] = facinv[i + 1] * (i + 1) % p;

扩展欧拉定理

洛谷 P5091

给你三个正整数,$a,m,b$,你需要求:$a^b \bmod m$。

$1\le a \le 10^9$,$1\le b \le 10^{20000000},1\le m \le 10^8$。

题解

扩展欧拉定理的内容:

\[a^b\equiv \begin{cases} a^b,&\,b<\varphi(p)\\ a^{b\bmod\varphi(p)+\varphi(p)},&b\ge\varphi(p) \end{cases} \pmod p\]

欧拉函数 $\varphi(x)$ 的值可以在分解质因数的同时计算。

我们可以边读入 $b$ 边取模。

套定理,顺便加个快速幂即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a, b, m;
bool flag;
inline int phi(int x) {
    int ret = x;
    for(int i = 2; i * i <= x; i++) {
        if(x % i == 0) {
            ret = ret / i * (i - 1);
            while(x % i == 0)   x /= i;
        }
    }
    if(x > 1)   ret = ret / x * (x - 1);
    return ret;
}
inline int qpow(int a, int b) {
    int ret = 1;
    while(b) {
        if(b & 1)   ret = (1ll * ret * a) % m;
        a = (1ll * a * a) % m;   
        b >>= 1;
    }
    return ret;
}
int main() {
    scanf("%d%d", &a, &m);
    int phi_m = phi(m); 
    char c = getchar();
    while(!isdigit(c))  c = getchar();
    while(isdigit(c)) {
        b = (b << 1) + (b << 3) + (c ^ 48);
        if(b >= phi_m)   b %= phi_m, flag = 1;
        c = getchar();
    }
    if(flag)    b += phi_m;
    printf("%d", qpow(a, b));
    return 0;
}

矩阵快速幂

洛谷 P3390

一个 $m \times n$ 的矩阵是一个由 $m$ 行 $n$ 列元素排列成的矩形阵列。即形如

\[A = \begin{bmatrix} a_{1 1} & a_{1 2} & \cdots & a_{1 n} \\ a_{2 1} & a_{2 2} & \cdots & a_{2 n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m 1} & a_{m 2} & \cdots & a_{m n} \end{bmatrix} \text{.}\]

本题中认为矩阵中的元素 $a_{i j}$ 是整数。

两个大小分别为 $m \times n$ 和 $n \times p$ 的矩阵 $A, B$ 相乘的结果为一个大小为 $m \times p$ 的矩阵。将结果矩阵记作 $C$,则

\[c_{i j} = \sum_{k = 1}^{n} a_{i k} b_{k j} \text{($1 \le i \le m$, $1 \le j \le p$).}\]

而如果 $A$ 的列数与 $B$ 的行数不相等,则无法进行乘法。

可以验证,矩阵乘法满足结合律,即 $(A B) C = A (B C)$。

一个大小为 $n \times n$ 的矩阵 $A$ 可以与自身进行乘法,得到的仍是大小为 $n \times n$ 的矩阵,记作 $A^2 = A \times A$。进一步地,还可以递归地定义任意高次方 $A^k = A \times A^{k - 1}$,或称 $A^k = \underbrace{A \times A \times \cdots \times A}_{k \text{ 次}}$。

特殊地,定义 $A^0$ 为单位矩阵

\(I = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix}\)。

给定 $n\times n$ 的矩阵 $A$,求 $A^k$。

$1\le n \le 100$,$0 \le k \le 10^{12}$,$\lvert A_{i,j}\rvert \le 1000$。

题解

按照题意重载一下运算符,然后像整数的快速幂一样打就行了。注意 ans 要初始化成单位矩阵。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 105, MOD = 1e9 + 7;
ll n, k;
inline ll read() {...}
inline void write(ll x) {...}
struct matrix {
    ll a[MAX_N][MAX_N];
    matrix() {memset(a, 0, sizeof(a));}
    void init() {for(int i = 1; i <= n; i++) a[i][i] = 1;}
    matrix operator * (const matrix &t) const {
        matrix ret;
        for(int k = 1; k <= n; k++) {
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    ret.a[i][j] = (ret.a[i][j] + a[i][k] * t.a[k][j] % MOD) % MOD; 
                }
            }
        }
        return ret;
    }
} A, ans;

int main() {
    n = read(), k = read();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            A.a[i][j] = read();
        }
    }
    ans.init();
    while(k) {
        if(k & 1)   ans = ans * A;
        A = A * A;
        k >>= 1;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            write(ans.a[i][j]);
            putchar(' ');
        }
        putchar('\n');
    }
    return 0; 
}

矩阵加速(数列)

洛谷 P1939

已知一个数列 $a$,它满足:

\[a_x= \begin{cases} 1 & x \in\{1,2,3\}\\ a_{x-1}+a_{x-3} & x \geq 4 \end{cases}\]

求 $a$ 数列的第 $n$ 项对 $10^9+7$ 取余的值。

$1 \leq T \leq 100$,$1 \leq n \leq 2 \times 10^9$。

题解

构造常系数矩阵

\[A=\begin{bmatrix} 1 & 0 & 1\\1 & 0 & 0\\ 0 & 1 & 0\end{bmatrix}\]

可知

\[\begin{bmatrix}f_{n-1}\\f_{n-2}\\f_{n-3}\end{bmatrix}\times A = \begin{bmatrix}f_{n}\\f_{n-1}\\f_{n-2}\end{bmatrix}\]

所以答案为 $A^{n-1}$ 的 第 $1$ 行第 $1$ 列。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

inline ll read() {...}
inline void write(ll x) {...}
struct matrix {
    ll a[5][5];
    matrix() {memset(a, 0, sizeof(a));}
    inline matrix operator * (const matrix &t) const {
        matrix ret;
        for(int k = 1; k <= 3; k++) {
            for(int i = 1; i <= 3; i++) {
                for(int j = 1; j <= 3; j++) {
                    (ret.a[i][j] += a[i][k] * t.a[k][j] % MOD) %= MOD;
                }
            }
        }
        return ret;
    }
} ans, A;
inline void init() {
    memset(A.a, 0, sizeof(A.a));
    memset(ans.a, 0, sizeof(ans.a));
    A.a[1][1] = A.a[1][3] = A.a[2][1] = A.a[3][2] = 1;
    for(int i = 1; i <= 3; i++) ans.a[i][i] = 1;
}
int main() {
    int T = read();
    while(T--) {
        int n = read(); n--;
        if(n <= 3) {
            write(1), putchar('\n');
            continue;
        }
        init();
        while(n) {
            if(n & 1)   ans = ans * A;
            A = A * A;
            n >>= 1;
        }
        write(ans.a[1][1]), putchar('\n');
    }
    return 0;
}

例题 斐波那契数列

洛谷 P1962

求斐波那契数列的第 $n$ 项 $F_n \bmod 10^9 + 7$。

题解

构造的常系数矩阵为

\[A=\begin{bmatrix} 1 & 1\\1 & 0\end{bmatrix}\]

于是

\[\begin{bmatrix}F_{n-1}\\F_{n-2}\end{bmatrix}\times A = \begin{bmatrix}F_{n}\\F_{n-1}\end{bmatrix}\]

所以答案为 $A^{n-1}$ 的 第 $1$ 行第 $1$ 列。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
inline ll read() {...}
inline void write(ll x) {...}

struct matrix {
    ll a[4][4];
    matrix() {memset(a, 0, sizeof(a));}
    inline matrix operator * (const matrix &t) const {
        matrix ret;
        for(int k = 1; k <= 2; k++) {
            for(int i = 1; i <= 2; i++) {
                for(int j = 1; j <= 2; j++) {
                    (ret.a[i][j] += a[i][k] * t.a[k][j] % MOD) %= MOD;
                }
            }
        }
        return ret;
    }
} A, ans;

int main() {
    ll n = read(); n--;
    A.a[1][1] = A.a[1][2] = A.a[2][1] = 1;
    ans.a[1][1] = ans.a[2][2] = 1;
    while(n) {
        if(n & 1)   ans = ans * A;
        A = A * A;
        n >>= 1;
    }
    write(ans.a[1][1]);
    return 0;
}

配合结论 $\gcd(F_x,F_y)=F_{\gcd(x,y)}$,这道题等价于 洛谷 P1306

Joy © 2023 Powered by Jekyll and Theme by solid

今日诗词API Valine 评论管理 Github