我试图使用说明从geeksforgeeks文章来实现快速幂,但它显示错误,而解决:https://www.spoj.com/problems/FIBOSUM/
谁能解释什么是错误的代码?我试图通过的范围开始前计算斐波那契数总和的给定范围内最后一个元素和元素的斐波那契数之和减去它们,但它表明TLE和不正确的答案。
import java.util.*;
import java.io.*;
class GFG {
public static int fib(int n) {
if(n<=1)
return n;
int f[][] = new int[][]{{1,1},{1,0}};
int g = power(f,n-1);
return g;
}
public static int power(int f[][],int n){
int b[][] = new int[][]{{1,1},{1,0}};
int sum = 1;
for(int i = 2;i<=n;i++){
multiply(f,b);
sum = sum+f[0][0];
}
return((sum+1)%1000000007);
}
public static void multiply(int f[][],int b[][]){
int x = f[0][0]*b[0][0]+f[0][1]*b[1][0];
int y = f[0][0]*b[0][1]+f[0][1]*b[1][1];
int z = f[1][0]*b[0][0]+f[1][1]*b[1][0];
int w = f[1][0]*b[0][1]+f[1][1]*b[1][1];
f[0][0] = x;
f[0][1] = y;
f[1][0] = z;
f[1][1] = w;
}
public static void main (String[] args) throws Exception {
Scanner s = new Scanner(System.in);
int t = s.nextInt();
for(int i = 1;i<=t;i++){
int n = s.nextInt();
int m = s.nextInt();
if(n!=0)
n = fib(n-1);
m = fib(m);
System.out.println((m-n)%1000000007);
}
}
}
你必须照顾底片为(M-N + MOD)MOD%