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
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;
扩展欧拉定理
给你三个正整数，$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;
}
矩阵快速幂
一个 $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;
}
矩阵加速（数列）
已知一个数列 $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;
}
例题 斐波那契数列
求斐波那契数列的第 $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。
♥