LC 70. Climbing Stairs

 1/**
 2 * @param {number} n
 3 * @return {number}
 4 */
 5var climbStairs = function(n) {
 6  const q = [[1, 1], [1, 0]]
 7  const res = pow(q, n)
 8  return res[0][0]
 9};
10
11const pow = (a, n) => {
12  let ret = [[1, 0], [0, 1]]
13  while (n > 0) {
14    if ((n & 1) === 1) {
15      ret = multiply(ret, a)
16    }
17    n >>= 1
18    a = multiply(a, a)
19  }
20  return ret
21}
22const multiply = (a, b) => {
23  const c = new Array(2).fill(0).map(() => new Array(2).fill(0))
24  for (let i = 0; i < 2; i++) {
25    for (let j = 0; j < 2; j++) {
26      c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]
27    }
28  }
29  return c
30}