洛谷题单指南-基础线性代数-P1962 斐波那契数列

原题链接：https://www.luogu.com.cn/problem/P1962

题意解读：求斐波那契数列第n项，n非常大

解题思路：

由于n非常大，直接递推必然超时，这里介绍一种常见优化递推的方法：矩阵快速幂。

具体来说，

100分代码：

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int MOD = 1e9 + 7;
struct Matrix
{LL a[5][5];Matrix(){memset(a, 0, sizeof(a));}Matrix operator * (const Matrix &to) 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] * to.a[k][j]) % MOD;return res;}
} G2, A, ans;
LL n;Matrix ksm(Matrix &a, LL b)
{Matrix res;res.a[1][1] = 1, res.a[2][2] = 1;while(b){if(b & 1) res = res * a;b >>= 1;a = a * a;  }return res;
}int main()
{cin >> n;if(n <= 2){cout << 1 << endl;return 0;}G2.a[1][1] = 1, G2.a[1][2] = 1; //G(2) = [F(2), F(1)]A.a[1][1] = 1, A.a[1][2] = 1, A.a[2][1] = 1, A.a[2][2] = 0; ans = G2 * ksm(A, n - 2);cout << ans.a[1][1] << endl;
}