斐波那契数列 矩阵乘法优化DP
求(f(n) \%1000000007)，(nle 10^{18})
矩阵乘法：(i imes k)的矩阵(A)乘(k imes j)的矩阵(B)得到(k imes k)的矩阵，其中第(i)列第(j)行的数就是(A)的第(i)行所有数与(B)的第(j)列分别相乘再相加
考虑使用矩阵乘法优化DP，为了最后得到(f(n))，我们设矩阵( ext{base})，使(egin{bmatrix} F_{n-1} & F_{n-2} end{bmatrix} imes base = egin{bmatrix} F_{n} & F_{n-1} end{bmatrix})，容易推得得(base=egin{bmatrix} 1 & 1 \ 1 & 0 end{bmatrix})
然后因为矩阵乘法可以使用快速幂优化，所以我们直接算出(base^{n-2})，答案即为$egin{bmatrix} 1 & 1 end{bmatrix} imes base^{n-2} $矩阵的第一行第一列
#include <cstdio>
#include <cstring>
#define MOD 1000000007
using namespace std;
long long n;
struct Mat{
long long a[3][3];
Mat(){memset(a, 0, sizeof a);}
Mat operator * (const Mat &b) const{
Mat 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)%MOD;
return res;
}
} ans, base;
void qpow(long long x){
while(x!=0){
if(x&1) ans=ans*base;
x>>=1;
base=base*base;
}
}
int main(){
scanf("%lld", &n);
if(n<=2){
puts("1");
return 0;
}
ans.a[1][1]=ans.a[1][2]=1;
base.a[1][1]=1,base.a[1][2]=1,base.a[2][1]=1,base.a[2][2]=0;
qpow(n-2);
printf("%lld", ans.a[1][1]);
return 0;
}