该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
k阶斐波那契数列的第k项的值。
常见的是2阶斐波那契数列。
例如： f[n]=f[n-1]+f[n-2]+f[n-3] 是三阶。
矩阵二分算法如下(JAVA代码，大数运算)：
import java.math.BigInteger;
import java.util.*;
public class fib {
private static BigInteger a[][] , b[][] ;
private static void mul(BigInteger x[][], BigInteger y[][], int n)
{
BigInteger sum = new BigInteger("0");
BigInteger tmp[][] = new BigInteger[n][n];
for(int i =0 ;i
for(int j =0 ; j
sum = BigInteger.ZERO;
for(int k =0 ; k
sum = sum.add( x[i][k].multiply( y[k][j]) );
}
tmp[i][j] = sum;
}
}
a = tmp;
return ;
}
private static void init(int n)
{
a= new BigInteger[n][n];
b = new BigInteger[n][n];
for(int i =0 ; i
for( int j =0 ; j
if(i == j+1 ){
a[i][j] = BigInteger.ONE;
}else{
a[i][j] = BigInteger.ZERO;
}
}
a[i][n-1] = BigInteger.ONE;
}
b = a ;
return ;
}
private static void fib(int n , int k){
if(k == 1 ) return ;
fib(n,k/2);
mul(a,a,n);
if(1 == k%2 ){
mul(a,b,n);
}
return;
}
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
while(true){
int n = cin.nextInt(),k = cin.nextInt();
init(n);
fib(n,k);
System.out.println(a[0][n-1]);
}
}
}