1function matMul(A, B) {
2 const n = A.length;
3 const C = Array.from({ length: n }, () => new Array(n).fill(0));
4 for (let i = 0; i < n; i++)
5 for (let j = 0; j < n; j++)
6 for (let k = 0; k < n; k++)
7 C[i][j] += A[i][k] * B[k][j];
8 return C;
9}
10function fibByMatrix(n) {
11 let result = [[1, 0], [0, 1]];
12 let base = [[1, 1], [1, 0]];
13 while (n > 0) {
14 if (n & 1) result = matMul(result, base);
15 base = matMul(base, base);
16 n >>= 1;
17 }
18 return result[0][1];
19}