算法能力提升之快速矩阵

今天还是给大家带来关于快速矩阵的算法思想，这部分类型题目还是重在解决时间复杂度过大的问题，同时要注意的是矩阵乘法重载的编写，这部分是关键。

题目描述

斐波那契数列：∗{F(1)=F(2)=1F(n)=F(n−1)+F(n−2)​​n>2,n∈N∗​
给定一个正整数 N，求F(N)在模109+7 下的值。

输入描述

第 1 行为一个整数 T，表示测试数据数量。

接下来的 TT 行每行包含一个正整数 N。

1≤T≤104，1≤N≤1018。

输出描述

输出共 T 行，每行包含一个整数，表示答案。

输入案例：

6
1
2
3
4
5
1000000000

输出案例：

1
1
2
3
5
21

代码部分：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int mod=1e9+7;
using vvl=vector<vector<ll>>;ll n;
vvl operator*(const vvl &a,const vvl &b){vvl ans(2,vector<ll>(2,0));for(int i=0;i<2;i++){for(int j=0;j<2;j++){for(int k=0;k<2;k++){ans[i][j]=(ans[i][j]+a[i][k]*b[k][j]%mod)%mod;}}}return ans;
}
ll solve(){cin>>n;vvl mat1={{0,1},{1,1}},matans={{1,0},{0,1}};//单位矩阵while(n){if(n&1)matans=matans*mat1;mat1=mat1*mat1;n>>=1;}return 1*matans[0][1];}
int main(){int t=1;cin>>t;while(t--){cout<<solve()<<'\n';}return 0;
}

核心原理：矩阵表示斐波那契递推

斐波那契数列的递推关系可以用矩阵乘法表示：

[F(n) F(n−1)​]=[11​ 10​]×[F(n−1) F(n−2)​]

进一步推广，通过连续的矩阵乘法可以得到：

[F(n)F(n−1)​]=[11 ​10​]n−2×[F(2)F(1)​]=[11​ 10​]n−2×[11​]

代码解析：

1. 矩阵乘法重载

using vvl = vector<vector<ll>>;  // 定义vvl为二维long long向量（矩阵）// 重载矩阵乘法运算符
vvl operator*(const vvl &a, const vvl &b) {vvl ans(2, vector<ll>(2, 0));  // 结果矩阵（2x2）for (int i = 0; i < 2; i++) {for (int j = 0; j < 2; j++) {for (int k = 0; k < 2; k++) {// 矩阵乘法：ans[i][j] = sum(a[i][k] * b[k][j]) mod modans[i][j] = (ans[i][j] + a[i][k] * b[k][j] % mod) % mod;}}}return ans;
}

2. 矩阵快速幂计算斐波那契数

ll solve() {cin >> n;  // 输入N// 递推矩阵：[[0,1],[1,1]]（与标准形式等价，只是行列顺序调整）vvl mat1 = {{0, 1}, {1, 1}};// 单位矩阵：初始结果矩阵（矩阵乘法的"1"）vvl matans = {{1, 0}, {0, 1}};// 矩阵快速幂：计算mat1的n次幂（通过二进制分解）while (n) {if (n & 1) {  // 若当前二进制位为1，将mat1乘入结果matans = matans * mat1;}mat1 = mat1 * mat1;  // 矩阵自乘（指数翻倍）n >>= 1;  // 右移一位，处理下一个二进制位}// 返回F(n)：根据矩阵乘法结果推导，此处取matans[0][1]return 1 * matans[0][1];
}

• (2, vector<ll>(2, 0))：调用 vector 的构造函数，参数表示 “创建一个包含 2 个元素的外层向量，每个元素都是 vector<ll>(2, 0)”。
  • 内层 vector<ll>(2, 0) 表示 “创建一个包含 2 个元素的 long long 向量，每个元素初始化为 0”。

因此，vvl ans(2, vector<ll>(2, 0)) 的实际效果是：
创建一个 2 行 2 列的二维向量（矩阵），所有元素初始化为 0，等价于：

vector<vector<ll>> ans(2, vector<ll>(2, 0));  // 没有别名时的写法

3. 为什么可以 vvl mat1 = {{0, 1}, {1, 1}} 这样初始化？

• {{0, 1}, {1, 1}} 是一个嵌套的初始化列表：外层列表 { {0,1}, {1,1} } 表示外层向量的两个元素。内层列表 {0,1} 和 {1,1} 分别表示两个内层向量的元素。

vvl mat1;
mat1.push_back(vector<ll>{0, 1});  // 第一行
mat1.push_back(vector<ll>{1, 1});  // 第二行