Generic Fibonacci

Main.java

import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner ds = new Scanner(System.in);
		int t = ds.nextInt(); // \n
		//long start_time = System.currentTimeMillis();
		for(int x = 0; x < t; x += 1) {
		  int i = ds.nextInt(); // \ 
			int A = ds.nextInt(); // \ 
			int B = ds.nextInt(); // \ 
			int C = ds.nextInt(); // \ 
			int D = ds.nextInt(); // \ 
			System.out.println(Long.toString(new Main(A, B, C, D).r_matrix(i)));
		}
		//long end_time = System.currentTimeMillis();
		//System.out.println("Time used (total): " + (end_time - start_time));
		//System.out.println("Time used (avg):   " + (end_time - start_time)/t);
	}

	private final int A, B, C, D;

	Main(int A, int B, int C, int D) {
		this.A = A;
		this.B = B;
		this.C = C;
		this.D = D;
	}

	// O(2^n) -- actually, it's in O(fib(n))
	long r(int n) {
		// require(n >= 0, n must be positive);
		return n < 2 ? (n == 0 ? A : B) : C*r(n-1) + D*r(n-2);
	}

	// O(1) - wrapper function
	long r_fast(int n) {
		return n < 2 ? (n == 0 ? A : B) : r_fast(n, 2, A, B);
	}

	// Tail-rec + linear
	private long r_fast(int n, int i, long prev_2, long prev_1) {
		long new_val = C*prev_1 + D*prev_2;
		return n == i ? new_val : r_fast(n, i+1, prev_1, new_val);
	}

	// Like r_fast, just tail-rec-optimized (manually, since JVM can't)
	long r_fast_optimized(int n) {
		if(n < 2) {
			return n == 0 ? A : B;
		}
		n -= 2;
		long prev = A;
		long new_val = B;
		// This guy highly optimized, all of n,new_val,prev and tmp could be in registers.
		do {
			long tmp = D*prev; // prev = prev_2
			prev = new_val;    // now prev = prev_1
			new_val = C*new_val + tmp;
			n -= 1;
		} while(n > 0); // check against null
		return new_val;
	}

	/**
	 * One step can be represented as:
	 * [R(n+1)] = [C D] [R(n)]
	 * [R(n)]   = [1 0] [R(n-1)]
	 * Since R(n+1) = C*R(n) + D*R(n-1)
	 *   and R(n)   = 1*R(n) + 0*R(n-1)
	 *
	 * If we now do a [[C D] [1 0]] ^ (n-1) we do n-1 steps and have R((n-1)+1) in the top value of the vector.
	 * Starting values are [B A] obviously.
	 */
	long r_matrix(int n) {
		if(n == 0) { return A; } // pow(-1) is not defined, catch this manually.
		Matrix init = step_matrix();
		Matrix dat_matrix = init.pow(n-1);
		return dat_matrix.mult_vec_1(B, A);
	}

	Matrix step_matrix() {
		Matrix matrix = new Matrix();
		matrix.a = C;
		matrix.b = D;
		matrix.c = 1;
		matrix.d = 0;
		return matrix;
	}

	/** @Immutable */	static class Matrix {
		// identity-matrix per default
		long a=1,b=0;
		long c=0,d=1;

		Matrix mult(Matrix o) {
			Matrix m = new Matrix();
			m.a = a*o.a + b*o.c;
			m.b = a*o.b + b*o.d;
			m.c = c*o.a + d*o.c;
			m.d = c*o.b + d*o.d;
			return m;
		}

		// O(log n)
                Matrix pow(int n) {
			// Return identity
			if(n <= 0) { return new Matrix(); }
			else if(n == 1) { return this; }
			else if (n == 2) { return mult(this); }
			else if (n % 2 == 0) { return pow(n/2).pow(2); }
			else { return pow(n-1).mult(this); }
		}

		// Return the upper value you get if you mult this matrix with [x y]
		long mult_vec_1(long x, long y) {
			return a*x+b*y;
		}
	}