大家都知道，斐波那契数列是满足如下性质的一个数列：
• f(1) = 1
• f(2) = 1
• f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)
请你求出 f(n) mod 1000000007 的值。
矩阵快速幂
斐波那契数列通项公式为$f[i]=f[i-1]+f[i-2]$
相当于DP的转移方程是一致的，那么初始矩阵 : $0 1$
不断去乘上状态转移矩阵，即不断进行矩阵运算，最终得到目标矩阵
如何去求状态转移矩阵呢？
当然是根据状态转移方程来列。
$0 1$
$1 1$
#include<iostream> #include<cstdio> #include<cmath> #define N 1005 #define ll long long #define mod 1000000007 using namespace std; struct Martixt { ll n,m,a[N][N]; } A,B,C; ll n; void mul_1() { for(int i=1; i<=2; i++) for(int j=1; j<=2; j++) B.a[i][j]=A.a[i][j],A.a[i][j]=0; for(int i=1; i<=2; i++) for(int j=1; j<=2; j++) for(int k=1; k<=2; k++) A.a[i][j]=(A.a[i][j]+B.a[i][k]*B.a[k][j]%mod)%mod; } void mul_2() { for(int j=1; j<=2; j++) B.a[1][j]=C.a[1][j],C.a[1][j]=0; for(int j=1; j<=2; j++) for(int k=1; k<=2; k++) C.a[1][j]=(C.a[1][j]+B.a[1][k]*A.a[k][j]%mod)%mod; } void matrix_pow() { for(; n; n>>=1,mul_1()) if(n&1) mul_2(); } int main() { scanf("%lld",&n); A.a[1][1]=0; A.a[1][2]=A.a[2][1]=A.a[2][2]=1; C.a[1][1]=0; C.a[1][2]=1; matrix_pow(); printf("%d",C.a[1][1]); return 0; }
原文：https://www.cnblogs.com/song-/p/9736765.html