矩阵快速幂求菲波那切数列

#include<cstdio> #include<cstring> using namespace std; struct Matrix{ long long x[2][2]; friend Matrix operator*(const Matrix &a,const Matrix &b){ Matrix temp; temp.clear(); for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) for(int k=0;k<=1;k++){ temp.x[i][j]+=a.x[i][k]*b.x[k][j]; temp.x[i][j];} return temp; } }ans={2,1,1,1},inc={1,1,1,0}; int main(){ long long m; scanf("%lld",&m); m-=3; while(m){ if(m&1) ans=ans*inc; inc=inc*inc; m>>=1; } printf("%lld",ans.x[0][0]); return 0;}