本文主要是介绍矩阵求斐波那契数列第n项，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
记一个板子 原博客在这
#include<bits/stdc++.h>using namespace std;
const int MAX = 10;
#define __int64 long long
#define Bit(n) 1<<n
#define CLR(arr, val) memset(arr,val,sizeof(arr))
const int mod = 1e9 + 7;class Matrix {
public:Matrix(int r, int c) : row(r), col(c) {}void Init() {CLR(map, 0);map[0][0] = map[0][1] = map[1][0] = 1;}void Unit() //初始化为单位矩阵{CLR(map, 0);for (int i = 0; i < row; i++)map[i][i] = 1;}int Result() const { return map[0][1] % mod; }friend Matrix operator*(const Matrix &, const Matrix &);int Pow(int);private:__int64 map[MAX][MAX];int row, col;
};Matrix operator*(const Matrix &M1, const Matrix &M2) //矩阵相乘模板
{Matrix M(M1.row, M2.col); //相乘之后矩阵的行和列会变化for (int i = 0; i < M1.row; i++)for (int j = 0; j < M2.col; j++) {M.map[i][j] = 0;for (int k = 0; k < M1.col; k++)M.map[i][j] += M1.map[i][k] * M2.map[k][j];M.map[i][j] %= mod;}return M;
}Matrix M(2, 2);int Matrix::Pow(int n) //矩阵快速幂
{Matrix temp(2, 2);temp.Init();for (int i = 0; Bit(i) <= n; i++) //利用二进制的思想求解{if (Bit(i) & n) M = M * temp;temp = temp * temp;}return M.Result();
}int main() {int k;scanf("%d", &k);while(k--){__int64 num;cin >> num;M.Unit();cout << M.Pow(num) << endl;}return 0;
}再搞一个矩阵的板子
struct Matrix {ll a[maxn][maxn];Matrix operator*(const Matrix &b) const {Matrix c;for (int i = 1; i <= k; i++) {for (int j = 1; j <= k; j++) {c.a[i][j] = 0;for (int u = 1; u <= k; u++) {c.a[i][j] = (c.a[i][j] + a[i][u] * b.a[u][j] % (mod - 1)) % (mod - 1);}}}return c;}Matrix pow(ll x) const {Matrix b = *this, r = *this;x--;while (x > 0) {if (x & 1) r = r * b;b = b * b;x >>= 1;}return r;}
};
这篇关于矩阵求斐波那契数列第n项的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
