NEWCH-Codechef October Challenge

NEWCH.cpp

/*
Problem : NEWCH,Codechef's October Challenge 2012
Author : Abhinav Shrivastava
Compiler : Codeblocks 10.05
Concept : Solution to Recurrence relation using Matrix Exponentiation
*/
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<math.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
#define mod 1000000007
#define  K 3
typedef long long int Int_64;
/*******************************************************************************************************************************/
//K is Dim
//Fn[i]=coeff_1*Fn(i-alpha)+coeff_2*Fn(i-Beta)+...+coeff_KFn(i-Zeta)
/******************************************************************************************************************************/
 
/*In Matrix Exponentiation All Arrays are 1 Based.
Function That Multiply the Two Matrices Matrix1 * Matrix 2
*/
 
//Variables
Int_64   **productMatrix;
Int_64   F1[K+1];
Int_64   **X;
Int_64   **T;
 
// Returns the Simple Matrix Multiplication of Two Matrices M1 and M2.
Int_64** Multiply(Int_64 **M1,Int_64 **M2)
{
	int i,j,k;
	productMatrix=(Int_64**)malloc((K+2) * sizeof(Int_64*));
	for(i=0;i<=K;++i)
		productMatrix[i]=(Int_64*)malloc((K+1) *sizeof(Int_64));
 
	for(i=1;i<=K;++i)
	{
		for(j=1;j<=K;++j)
		{
			productMatrix[i][j]=0;
			for(k=1;k<=K;++k)
			{
				productMatrix[i][j]=( productMatrix[i][j]+(M1[i][k]*M2[k][j]) ) % mod;
			}
		}
	}
	return productMatrix;
}
/*
To solve    :(Matrix)^P ;
The Following is Logn solution.
 
|Return  Matrix                      ->if P==1;
(Matrix^P)=|Return  (Matrix)*(Matrix^(P-1))     ->if P is Odd
|Return  (Matrix^P/2)*(Matrix^P/2)   ->if P is Even
*/
Int_64** Power(Int_64 **A,Int_64 p)
{
	if (p == 1)
		return A;
	if (p % 2)
		return  Multiply(A, Power(A, p-1));
	X = Power(A, p/2);
	return  Multiply(X, X);
}
 
Int_64 solve(Int_64 N)
{
	int i,j;
	Int_64 result=0;
	/*
	Example consider the Recurrence Relation to be
	Fn(N)=(2*Fn(N-1)+2*Fn(N-2))
	Fn(1)=1,Fn(K=2)=3;
 
	Step 1:
	As Every DP starts with a base case ,so Similar is the Case Here
	Base case is a column Vector F1
	Eg .When FN[i]=FN[i-1]+4*FN[i-2]+6*FN[i-3]+8*FN[i-4]
 
	        |FN(0)=NULL |
            |      FN(1)      |
	F1:   |      FN(2)      |
            |       FN(3)     |
            |     FN(K=4)   |(K*1 Dimension)
	*/
	F1[2]=12;
	F1[3]=24;
	F1[4]=84;
	F1[5]=240;
			/*Step 2: Fill the T Matrix
	Eg:FN[i]=FN[i-1]+4*FN[i-2]+6*FN[i-3]+8*FN[i-4];
                    |N  N  N N  N |
                    |N  0  1  0  0 |
	T(K*K)=    |N  0  0  1  0 |
                    |N  0  0  0  1 |
                    |N  8  6  4  1 |
 
     1, 1, 1,
	1, 0, 0,
	0, 1, 0,
	*/
	T=(Int_64**)malloc((K+2) *sizeof(Int_64*));
	for(i=0;i<=K;i++)
		T[i]=(Int_64*)malloc((K+1) *sizeof(Int_64));
		for(i=0;i<=K;i++)
		   for(j=0;j<=K;j++)
		      T[i][j]=0;
T[1][1]=0,T[1][2]=1,T[1][3]=0,T[2][1]=0,T[2][2]=0,T[2][3]=1,T[3][1]=0,T[3][2]=3,T[3][3]=2;
 
	/*Step 3:
	Apply :: T=(T^N-1)
	*/
 
		if(N==2) 	return F1[2];
	else	if(N==3)  	return F1[3];
	else	if(N==4)  	return F1[4];
    else if(N==5)  	return F1[5];
 
	T=Power(T,N-1);
 
	/*Step 4:
	So the Overall Answer is::
	First row of (T*F1).
	*/
	result=0;
	for(i=1;i<=K;i++)
		{   //  cout<<"T[1]["<<i<<"] : "<<T[1][i]<<endl;
	    //cout<<"T[1]["<<i<<"]*F1["<<i<<"] = "<<T[1][i]*F1[i]<<endl;
		result=(result+T[1][i]*F1[i])%mod;
		//cout<<"result ["<<i<<"] = "<<result<<endl;
	}
	return result;
 
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    { Int_64 n,h;
        scanf("%lld",&n);
          printf("%d\n",solve(n));
    }
    return 0;
}
 

Matrix Exponentiation is used to calulate things fastly in O(logn) time