Created
October 17, 2012 18:25
-
-
Save abhinav1592/3907192 to your computer and use it in GitHub Desktop.
NEWCH-Codechef October Challenge
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Matrix Exponentiation is used to calulate things fastly in O(logn) time