该楼层疑似违规已被系统折叠 隐藏此楼查看此楼

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]);

}

}

}