Matrix Exponentiation, Recurrence Eqn, Fibonacci

SPOJ-BUZZOFF.cpp

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const long long int mod = 1000000007;
class _matrix{ 
  public: 
		long long int x[2][2];
		int n,m;
		_matrix() { 
			memset(x, 0, sizeof(x)); 
			n=m=2; 
		}
		void print(){
			for(int i=0;i<2;i++){
				for(int j=0;j<2;j++)
					cout << x[i][j] << ' ';
					cout << endl;
			}
		}
	};
	
int N;

class _matrix mul(class _matrix a, class _matrix b)
{
	class _matrix r;
	for(int i=0;i<a.n;i++)
		for(int j=0;j<a.m;j++)
		{
			unsigned long long res=0;
			for(int k=0;k<b.n;k++)
				res += 1LL*a.x[i][k]*b.x[k][j];
			r.x[i][j] = res % mod;
		}
return r;			
}

class _matrix pow(class _matrix a, long long int n)
{
	if(n==1)
		return a;
	class _matrix x = pow(a,n/2);
	class _matrix r = mul(x,x);
	if(n%2==1)
		r=mul(r,a);
	return r;			
}
/*
fn(n)=fn(n)
fn(n+1)=fn(n) + fn(n-1)
1 1
1 0
1 1 a 
1 0 b 
1 1 a+b=c 
1 0 a
1 1 c+a
1 0 c   
*/
int main()
{
	class _matrix a;
	a.x[0][0]=1;
	a.x[0][1]=1;
	a.x[1][0]=1;
	long long int tc, N;
	cin >> tc;
	while(tc--){
	cin >> N;
	class _matrix r1=pow(a,N+2);
	//r.print();
	//r1.print();
	// FIB SEQ 1 1 2 3 5 8 13 21
	// SUM OF FIRST N FIBO F(N+2)-1
	// CURRENT SEQ 1 2 3 5 8 13 21
	// SUM OF FIRST N CURR SEQ F(N+2)-2
	long long res=r1.x[0][0] - 2;
	if(res<0)
		res+=mod;
	cout << res << endl;
	}
}