AcWing 21. 斐波那契数列
原题链接
简单
作者:
lyxcqupt
,
2024-04-09 14:41:12
,
所有人可见
,
阅读 11
用快速幂装个逼
class Solution {
public int Fibonacci(int n) {
return fib(n);
}
public int fib(int n){
int[][] a = new int[][]{{0,1},{0,0}};
int[][] f = new int[][]{{0,1},{1,1}};
while(n != 0){
if((n & 1) == 1) a = mul(a,f);
f = mul(f,f);
n >>= 1;
}
return a[0][0];
}
public int[][] mul(int[][] a,int[][] b){
int[][] c = new int[2][2];
for(int i = 0;i < 2;i++){
for(int j = 0;j < 2;j++){
for(int k = 0;k < 2;k++){
c[i][j] = c[i][j] + a[i][k] * b[k][j];
}
}
}
return c;
}
}