For solving the matrix exponentiation we are assuming a
linear recurrence equation like below:
F(n) = a*F(n-1) + b*F(n-2) + c*F(n-3) for n >= 3
. . . . . Equation (1)
where a, b and c are constants.
For this recurrence relation, it depends on three previous values.
Now we will try to represent Equation (1) in terms of the matrix.
[First Matrix] = [Second matrix] * [Third Matrix]
| F(n) | = Matrix 'C' * | F(n-1) |
| F(n-1) | | F(n-2) |
| F(n-2) | | F(n-3) |
Dimension of the first matrix is 3 x 1 .
Dimension of the third matrix is also 3 x 1.
So the dimension of the second matrix must be 3 x 3
[For multiplication rule to be satisfied.]
Now we need to fill the Matrix 'C'.
So according to our equation.
F(n) = a*F(n-1) + b*F(n-2) + c*F(n-3)
F(n-1) = F(n-1)
F(n-2) = F(n-2)
C = [a b c
1 0 0
0 1 0]
Now the relation between matrix becomes :
[First Matrix] [Second matrix] [Third Matrix]
| F(n) | = | a b c | * | F(n-1) |
| F(n-1) | | 1 0 0 | | F(n-2) |
| F(n-2) | | 0 1 0 | | F(n-3) |
Generalised Fibonacci numbers
Consider the generalized Fibonacci number G, which is dependent on a, b and c as follows :-
G(1) = 1
G(2) = 1
G(n) = aG(n-1) + bG(n-2) + c.
Your task is to calculate G(n)%m for given values of n and m.
Lets assume the initial values for this case :-
F(0) = 0
F(1) = 1
F(2) = 1
So, we need to get F(n) in terms of these values.
So, for n = 3 Equation (1) changes to
| F(3) | = | a b c | * | F(2) |
| F(2) | | 1 0 0 | | F(1) |
| F(1) | | 0 1 0 | | F(0) |
Now similarly for n = 4
| F(4) | = | a b c | * | F(3) |
| F(3) | | 1 0 0 | | F(2) |
| F(2) | | 0 1 0 | | F(1) |
- - - - 2 times - - -
| F(4) | = | a b c | * | a b c | * | F(2) |
| F(3) | | 1 0 0 | | 1 0 0 | | F(1) |
| F(2) | | 0 1 0 | | 0 1 0 | | F(0) |
So for n, the Equation (1) changes to
- - - - - - - - n -2 times - - - - -
| F(n) | = | a b c | * | a b c | * ... * | a b c | * | F(2) |
| F(n-1) | | 1 0 0 | | 1 0 0 | | 1 0 0 | | F(1) |
| F(n-2) | | 0 1 0 | | 0 1 0 | | 0 1 0 | | F(0) |
| F(n) | = [ | a b c | ] ^ (n-2) * | F(2) |
| F(n-1) | [ | 1 0 0 | ] | F(1) |
| F(n-2) | [ | 0 1 0 | ] | F(0) |
So we can simply multiply our Second matrix n-2 times and then multiply it with the third matrix to get the result. Multiplication can be done in (log n) time using Divide and Conquer algorithm for power
Let us consider the problem of finding n'th term of a series defined using below recurrence.
n'th term,
F(n) = F(n-1) + F(n-2) + F(n-3), n >= 3
Base Cases :
F(0) = 0, F(1) = 1, F(2) = 1
e can find n'th term using following :
Putting a = 1, b = 1 and c = 1 in above formula
| F(n) | = [ | 1 1 1 | ] ^ (n-2) * | F(2) |
| F(n-1) | [ | 1 0 0 | ] | F(1) |
| F(n-2) | [ | 0 1 0 | ] | F(0) |
#include <bits/stdc++.h>
#define MOD 1000000007
#define endll "\n";
using namespace std;
#define N 3
long long int mat[N][N],res[N][N];
void mul(long long int res[N][N],long long int mat[N][N],long long int m){
long long int res1[3][3];
memset(res1,0,sizeof(res1));
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
for(int k=0;k<3;k++){
res1[i][j]+=(res[i][k]*mat[k][j]);
res1[i][j]%=m;
}
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
res[i][j]=res1[i][j];
}
}
}
void mat_exp(long long int n,long long int m){
while(n>0){
if(n&1) mul(res,mat,m);
mul(mat,mat,m);
n/=2;
}
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
int t;cin>>t;
while(t--){
long long int a,b,c,n,m;cin>>a>>b>>c>>n>>m;
memset(res,0,sizeof(res));
res[0][0]=res[1][1]=res[2][2]=1;
mat[0][0]=a;
mat[0][1]=b;
mat[0][2]=mat[1][0]=mat[2][2]=1;
mat[1][1]=mat[1][2]=mat[2][0]=mat[2][1]=0;
if(n<=2){
cout<<1<<endll;
}
else{
mat_exp(n-2,m);
cout<<(res[0][0]+res[0][1]+c*res[0][2])%m<<endll;
}
}
return 0;
}
