Linked Questions

Popular Questions

Error while implementing matrix exponentiation

Asked by At

I tried to implement fast exponentiation using explanation from article on geeksforgeeks but it shows error while solving: https://www.spoj.com/problems/FIBOSUM/

Can anyone explain what’s wrong with the code? I tried by computing Fibonacci sum for last element of given range and Fibonacci sum of element before beginning of range and subtracted them, but it shows tle and incorrect answer.

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

        }
    }
}

Related Questions