# O(log n) solution

• Classic fibonacci:

``````#define DIM 2
struct M{
int t[DIM][DIM];
M(){
for(int i = 0; i < DIM; i++){
for(int j = 0; j < DIM; j++){
t[i][j] = 0;
}
}
}
};

M operator *(const M& a, const M& b){
M result;
for(int i = 0; i < DIM; i++){
for(int j = 0; j < DIM; j++){
for(int k = 0; k < DIM; k++){
result.t[i][j] += a.t[i][k] * b.t[k][j];
}
}
}
return result;
}
M pot(const M& a, int p){
if(p == 0){
M result;
for(int i = 0; i < DIM; i++){
result.t[i][i] = 1;
}
return result;
}
if(p & 1){
return a * pot(a, p - 1);
} else{
M temp = pot(a, p / 2);
return temp * temp;
}

}
class Solution {
public:
int climbStairs(int n) {
if(n <= 1){
return 1;
}
M baseMatrix;
baseMatrix.t[0][0] = 1;
baseMatrix.t[0][1] = 1;
M fibMatrix;
fibMatrix.t[0][0] = 0;
fibMatrix.t[0][1] = 1;
fibMatrix.t[1][0] = 1;
fibMatrix.t[1][1] = 1;
fibMatrix = pot(fibMatrix, n - 1);
baseMatrix = baseMatrix * fibMatrix;
return baseMatrix.t[0][1];
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.