使用矩阵来解，当然可以用递归，递推去做
如图：
所以f(n)便是左面矩阵的n-1次方后第1行榜首列的数字
class Solution {
public:
struct Matrix//矩阵贮存
{
long long mat[3][3];
};
Matrix e;//单位矩阵
Matrix Mul(Matrix a, Matrix b)//矩阵相乘
{
Matrix temp;
for(int i = 1; i <= 2; i++)
for(int j = 1; j <= 2; j++)
temp.mat[i][j] = 0;
for(int i = 1; i <= 2; i++)
{
for(int j = 1; j <= 2; j++)
{
for(int k = 1; k <= 2; k++)
{
temp.mat[i][j] += a.mat[i][k] * b.mat[k][j];
}
}
}
return temp;
}
Matrix quickpow(Matrix a, int N)//快速幂
{
for(int i = 1; i <= 2; i++)//初始单位矩阵
e.mat[i][i] = 1;
Matrix res = e;
while(N)
{
if(N & 1)
res = Mul(res, a);
a = Mul(a, a);
N>>=1;
}
return res;
}
int fib(int N) {
if(N<=0)
return 0;
if(N == 1)
return 1;
Matrix st;
st.mat[1][1] = 1;
st.mat[1][2] = 1;
st.mat[2][1] = 1;
st.mat[2][2] = 0;
Matrix result = quickpow(st, N);
return result.mat[1][1];
}
};
