[链接登录后可见]
如果主题加载失败可以刷新一下
这周博客园在整改，暂时看不了
定义
矩阵，类似于一个二维数组
\begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}
主对角线：对于矩阵 A，主对角线是指 A_{i, i} 上的元素
单位矩阵 I：主对角线元素为 1，其他元素为 0 的矩阵
矩阵的逆
设一个矩阵 A，A 的逆矩阵 P 是使得 A \times P = I 的矩阵
可以用高斯消元的方式来求（暂时不会，先咕咕）
矩阵加（减）法
对应位置元素相加减
如，设矩阵 A,B，有 A \pm B = C，那么对于 C 中所有元素都有
C_{i, j} = A_{i, j} \pm B_{i, j}
注：矩阵加（减）法只有在矩阵大小相同时才有意义
矩阵乘法
设 A,B 两个矩阵，大小分别为 P \times M,M \times Q，设 C = A \times B，那么对于 C 中的每个元素，都有：
C_{i, j} = \sum_{k = 1}^{M}A_{i, k} \times B_{k, j}
通俗的讲，在矩阵乘法中，结果 C 矩阵的第 i 行第 j 列的数，就是由矩阵 A 第 i 行 M 个数与矩阵 B 第 j 列 个数分别相乘再相加得到的。
矩阵乘法满足结合律，但并不满足交换律
注：矩阵乘法只有在第一个矩阵的列数和第二个矩阵的行数相同时才有意义
优化
改变枚举顺序（粘个[链接登录后可见]的代码）
// 以下文的参考代码为例
inline mat operator*(const mat& T) const {
mat res;
for (int i = 0; i < sz; ++i)
for (int j = 0; j < sz; ++j)
for (int k = 0; k < sz; ++k) {
res.a[i][j] += mul(a[i][k], T.a[k][j]);
res.a[i][j] %= MOD;
}
return res;
}
// 不如
inline mat operator*(const mat& T) const {
mat res;
int r;
for (int i = 0; i < sz; ++i)
for (int k = 0; k < sz; ++k) {
r = a[i][k];
for (int j = 0; j < sz; ++j)
res.a[i][j] += T.a[k][j] * r, res.a[i][j] %= MOD;
}
return res;
}
实现
采用二维数组模拟矩阵
为了使用方便，通常把矩阵封装到一个结构体里，并重新定义矩阵运算
参考代码：
struct Matrix{
int a[size][size];
Matrix(){ memset(a, 0, sizeof a); }
Matrix operator + (const Matrix &b) const{
Matrix res;
for(int i = 1; i <= size; ++i)
for(int j = 1; j <= size; ++j)
res.a[i][j] = a[i][j] + b.a[i][j];
return res;
}
Matrix operator - (const Matrix &b) const{
Matrix res;
for(int i = 1; i <= size; ++i)
for(int j = 1; j <= size; ++j)
res.a[i][j] = a[i][j] - b.a[i][j];
return res;
}
Matrix operator * (const Matrix &b) const{
Matrix res;
for(int i = 1; i <= size; ++i)
for(int j = 1; j <= size; ++j)
for(int k = 1; k <= size; ++k)
res.a[i][j] = (res.a[i][j] + a[i][j] * b.a[i][j]) % mod;
return res;
}
};
矩阵快速幂
其实和普通快速幂没啥两样
Code
void quick_pow(int p){
while(p){
if(p & 1) ans = ans * base;
base = base * base;
p >>= 1
}
}
甚至也可以将它封装到结构体内
Matrix operator ^ (const LL x) const{
Matrix res, base;
for(int i = 1; i <= size; ++i) res.a[i][i] = 1;//初始化res矩阵
for(int i = 1; i <= size; ++i)
for(int j = 1; j <= size; ++j)
base.a[i][j] = a[i][j] % mod;
while(x) {
if(x & 1) res = res * base;
base = base * base;
x >>= 1;
}
return res;
}
例题
[链接登录后可见]
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int n, k;
struct Matrix{
int a[101][101];
Matrix() {memset(a, 0, sizeof a);};
Matrix operator * (const Matrix &b) const {
Matrix res;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
for(int k = 1; k <= n; ++k)
res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % mod;
return res;
}
}jz, ans;
int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return f ? -s : s;
}
void quick_pow(Matrix jz, int p, int mod){
ans = jz;
for( ; p; p >>= 1){
if(p & 1) ans = ans * jz;
jz = jz * jz;
}
}
signed main()
{
n = read(), k = read();
for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) jz.a[i][j] = read();
quick_pow(jz, k - 1, mod);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j){
printf("%lld ", ans.a[i][j]);
}
puts("");
}
return 0;
}
矩阵加速递推
矩阵加速递推斐波那切数列
[链接登录后可见]
发现如下关系：
对于第 n - 1 项，有：
\begin{bmatrix}
f_{n - 1} & f_{n - 2} \\
0 & 0
\end{bmatrix} \times \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix} = \begin{bmatrix}
f_{n} & f_{n - 1} \\
0 & 0
\end{bmatrix}
所以，若求第 n 项,有
\begin{bmatrix}
1 & 1 \\
0 & 0
\end{bmatrix} \times {\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}
}^{n - 2} = \begin{bmatrix}
f_{n} & f_{n - 1} \\
0 & 0
\end{bmatrix}
最后直接输出答案即可，如果 n \le 2 ，直接输出 1
例题
[链接登录后可见]
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int mod = 1e9+7;
int n;
struct Matrix{
int a[3][3];
Matrix(){memset(a, 0, sizeof a);}
Matrix operator * (const Matrix &b) const{
Matrix res;
for(int i = 1; i <= 2; ++i)
for(int j = 1; j <= 2; ++j)
for(int k = 1; k <= 2; ++k)
res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % mod;
return res;
}
}ans, base;
int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return f ? -s : s;
}
void quick_pow(int p){
while(p){
if(p & 1) ans = ans * base;
base = base * base;
p >>= 1;
}
}
signed main()
{
n = read();
if(n <= 2) { printf("1"); return 0; }
base.a[1][1] = base.a[1][2] = base.a[2][1] = 1;
base.a[2][2] = 0;
ans.a[1][1] = ans.a[1][2] = 1;
ans.a[2][1] = ans.a[2][2] = 0;
quick_pow(n - 2);
printf("%lld", ans.a[1][1] % mod);
return 0;
}
[链接登录后可见]
注意此时的base矩阵为
\begin{bmatrix}
1 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0
\end{bmatrix}
Code
/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl
using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;
struct Matrix{
int a[4][4];
Matrix() { memset(a, 0, sizeof a); }
Matrix operator * (const Matrix &b) const{
Matrix res;
for(int i = 1; i <= 3; ++i)
for(int j = 1; j <= 3; ++j)
for(int k = 1; k <= 3; ++k)
res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % mod;
return res;
}
Matrix operator ^ (const long long x) const{//重载快速幂，手感绝对丝滑
Matrix res, base;
for(int i = 1; i <= 3; ++i) res.a[i][i] = 1;
for(int i = 1; i <= 3; ++i)
for(int j = 1; j <= 3; ++j)
base.a[i][j] = a[i][j];
while(x){
if(x & 1) res = res * base;
base = base * base;
x >>= 1;
}
return res;
}
}jz, base, ans;
int T, n;
int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
return f ? -s : s;
}
signed main()
{
jz.a[1][1] = jz.a[1][2] = jz.a[1][3] = 1;
base.a[1][1] = base.a[2][3] = base.a[1][2] = base.a[3][1] = 1;
T = read();
while(T--){
n = read();
if(n <= 3){ printf("1\n"); continue; }
ans = jz * (base ^ (n - 3));
printf("%lld\n", ans.a[1][1]);
}
return 0;
}
