As these new editorials for SEPT12 were released, the interest in matrix exponentiation grew a lot, and I will try to provide a relatively complete, yet simple tutorial on the most simple recurrence relationships and how they can be written in the matrix form.
- Advantages of using matrix form instead of the recurrence relationship itself
To use matrix exponentiation it's first necessary to understand why we would want to use it... After all, methods such as classic DP and/or memoization are available and they are easier to code.
The great advantage of matrix exponentiation is that its running time is simply O(k^3 * logN)(for a matrix of dimensions k*k) which is critical when we are dealing with values as large as 10^15, for example. It is used when the recursive relationship we derived is somehow entangled, in the sense that the values it takes depend on more than one of the previous values...Using the base cases of the recurrence relation and a repeated squaring/fast exponentiation algorithm, we have a very efficent way of dealing with large input values :D I will try to illustrate this with an example, the Tribonacci Numbers.
For those of you who had never heard the name before, this sequence of numbers is an "expansion" of the fibonacci sequence that includes a third term on the sum of the previous two, such that the formula looks like:
F(n) = F(n-1) + F(n-2) + F(n-3), F(1) = 1; F(2) = 1; F(3) = 2
as stated on WolframMathworld.
Of course, all the problems that arose when we tried to compute the fibonnaci numbers via dp or any other way become a lot more complicated with tribonacci numbers, and for N as large as 10^15, using dp will always be very slow, regardless of the time limit.
- Understanding Matrix exponentiation
The basic idea behind matrix exponentiation, as stated earlier is to use the base cases of the recurrence relationship in order to assemble a matrix which will allow us to compute values fast.
On our case we have:
F(1) = 1
F(2) = 1
F(3) = 2
And we now have a relationship that will go like this:
|f(4)| = MATRIX * |f(1)|
|f(3)| |f(2)|
|f(2)| |f(3)|
Now all that is left is to assemble the matrix... and that is done based both on the rules of matrix multiplication and on the recursive relationship... Now, on our example we see that to obtain f(4), the 1st line of the matrix needs to be composed only of ones, as f(4) = 1 f(3) + 1 f(2) + 1* f(1).
Now, denoting the unknown elements as *, we have:
|f(4)| = |1 1 1| * |f(1)|
|f(3)| |* * *| |f(2)|
|f(2)| |* * *| |f(3)|
For the second line, we want to obtain f(3), and the only possible way of doing it is by having:
|f(4)| = |1 1 1| * |f(1)|
|f(3)| |0 0 1| |f(2)|
|f(2)| |* * *| |f(3)|
To get the value of f(2), we can follow the same logic and get the final matrix:
|1 1 1|
|0 0 1|
|0 1 0|
To end it, we now need to generalize it, and, as we have 3 base cases, all we need to do to compute the Nth tribonacci number in O(logN) time, is to raise the matrix to the power N -3 to get:
|f(n)| = |1 1 1|^(N-3) * |f(1)|
|f(n-1)| |0 0 1| |f(2)|
|f(n-2)| |0 1 0| |f(3)|
The power of the matrix can now be computed in O(logN) time using repeated squaring applied to matrices and the method is complete... Below is the Python code that does this, computing the number modulo 10000000007.
def matrix_mult(A, B):
C = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
for i in range(3):
for j in range(3):
for k in range(3):
C[i][k] = (C[i][k] + A[i][j] * B[j][k]) % 1000000007
return C
def fast_exponentiation(A, n):
if n == 1:
return A
else:
if n % 2 == 0:
A1 = fast_exponentiation(A, n/2)
return matrix_mult(A1, A1)
else:
return matrix_mult(A, fast_exponentiation(A, n - 1))
def solve(n):
A = [[1,1,1],[0,0,1],[0,1,0]]
A_n = fast_exponentiation(A,n-3)
return A_n[0][0] + A_n[0][1] + A_n[0][2]*2
/***********************************FIBONACHI USING MATRIX EXPONENTIATION ******************/
##include<iostream>
using namespace std;
#include<bits/stdc++.h>
void matmult(long long int a[][2],long long int b[][2],long long int c[][2],long long int M)//multiply matrix a and b. put result in c
{
long long int i,j,k;
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
c[i][j]=0;
for(k=0;k<2;k++)
{
c[i][j]+=(a[i][k]*b[k][j]);
c[i][j]=c[i][j]%M;
}
}
}
}
void matpow(long long int Z[][2],long long int n,long long int ans[][2],long long M)
//find ( Z^n )% M and return result in ans
{
long long int temp[2][2];
//assign ans= the identity matrix
ans[0][0]=1;
ans[1][0]=0;
ans[0][1]=0;
ans[1][1]=1;
long long int i,j;
while(n>0)
{
if(n&1)
{
matmult(ans,Z,temp,M); // z*arr aand storing in ans
for(i=0;i<2;i++)
for(j=0;j<2;j++)
ans[i][j]=temp[i][j];
}
matmult(Z,Z,temp,M);// z*z increasing power of z
for(i=0;i<2;i++)
for(j=0;j<2;j++)
Z[i][j]=temp[i][j];
n=n/2;
}
return;
}
long long int findFibonacci(long long int n,long long int M)
{
long long int fib;
if(n>2)
{
long long int Z[2][2]={{1,1},{1,0}},result[2][2];//modify matrix a[][] for other recurrence relations
matpow(Z,n-2,result,M);
fib=result[0][0]*1 + result[0][1]*0; //final multiplication of Z^(n-2) with the initial terms of the series
}
else
fib=n-1;
return fib;
}
int main()
{
long long int n,m;
while(scanf("%lld %lld",&n,&m)==2)
{
long long int kk=1;
for(int i=0;i<m;i++) kk*=2;
//cout<<kk<<endl;
long long int ll=findFibonacci(n+1,kk);
cout<<ll<<endl;
}
return 0;
}
NOTE ---- NOTE FOR MATRIX MUMTIPLICAION PART WE CAN ALSO DECREASE TIME BY USING STRASSION ALGO
OF FORE RUSHION ALGO FOR BINARY MATRIX
*--------------------------------------------CODECHEF NEW START -----------------------------------------****
My Fair Coins
There are coins of 2 different denominations in Crazyland, 1-cent coins and 2-cent coins. As all the coins do, even these coins have two faces, i.e. heads and tails.
Your task is to find out the the number of ways to create a linear arrangement of these coins so that their sum is N cents. The only condition on the linear arrangement is that
the first coin in the arrangement should always face heads. All other coins could either face head or face tail.
Take N = 2 as an example. The possible arrangements are (1H, 1H), (2H), (1H, 1T), where H is heads and T is tails.
Therefore there are 3 possible arrangements that sum up to 2-cents.
Note
While counting make sure that you count heads and tails as different.
Input
First line contains T, the number of cases.
T lines follow, each containing a single number N, the required sum.
Constraints
0 <= T <= 10000
1 <= N <= 1000000000
Output
For each case the output should be a single integer representing the number of such arrangements possible. As this can be very large print it modulo 1000000007.
Sample Input
3
1
2
3
Sample Output
1
3
8
********************************************EDITORIAL************************************************
PROBLEM:
There are infinite coins of two types - of value 1 and of value 2. All coins have two sides - heads and tails. You're to find out number of ways of arranging some coins such that their sum is equal to N (input) and the first coin is heads up.
QUICK EXPLANATION:
Let f(N) denote number of ways of arranging some coins such that their sum is equal to N and the first coin is heads up. Then it can be shown that f(N) = 2 (f(N-1) + f(N-2) ) with f(1) = 1 and f(2) = 3. Using matrix exponentiation, f(N)can be computed in time O(log N).
DETAILED EXPLANATION:
Let f(n, H) denote the number of ways of arranging coins such that their sum is n, and the first coin is heads up. Similarly let f(n, T) denote the number of ways of arranging coins such that their sum is n and first coin is tails up.
Our original problem is to find out f(n, H).
Here are our three claims:
f(n, H) = f(n, T)
f(n, H) = f(n-1, H) + f(n-1, T) + f(n-2, H) + f(n-2, T)
f(n, H) = 2 * ( f(n-1, H) + f(n-2, H) )
Let's see why each of these claims hold:
f(n, H) = f(n, T)
This is true because if we invert every coin of an arrangement with sum of n and first coin heads up, we get an arrangement with sum of n with first coin tails up. It is easy to see that it is infact a bijection. Hence the claim.
f(n, H) = f(n-1, H) + f(n-1, T) + f(n-2, H) + f(n-2, T)
This is the chief step of the problem : Let's look at a particular arrangement with sum of n and first coin heads up. First coin is either of value 1 or of value 2. In first case, sum of remaining coins is n-1 and their first coin could be either heads up or heads down. f(n-1, H) + f(n-1, T) account for such case. In other case, when first coin is of value 2, sum of remaining coins is n-2 and they could either be heads up or tails up. f(n-2, H) + f(n-2, T) account for these. So total : f(n, H) = f(n-1, H) + f(n-1, T) + f(n-2, H) + f(n-2, T) holds.
f(n, H) = 2 * ( f(n-1, H) + f(n-2, H) )
This follows from claims 1 and 2 naturally :)
Now we can drop H from the notation to get f(n) = 2 f(n-1) + 2 f(n-2) with base case of this recurrence as f(1) = 1and f(2) = 3. We can use matrix exponentiaion to solve for this recurrence. For those of you who don't know this very useful technique, I'm providing a short description here itself.
Let's write it in form of matrices:
[ f(n) f(n-1) ] = [ f(n-1) f(n-2) ] * | 2 1 |
| 2 0 |
You can verify that this is nothing but the recurrence we just wrote. Special property of writing it in this form is we [ f(n-1) f(n-2) ] is exactly of the same form as [ f(n) f(n-1) ] and so we can in turn expand it to get:
[ f(n) f(n-1) ] = [ f(n-2) f(n-3) ] * | 2 1 | * | 2 1 |
| 2 0 | | 2 0 |
We can continue expanding term on right handside till we get :
[ f(n) f(n-1) ] = [ f(2) f(1) ] * | 2 1 |^(n-2)
| 2 0 |
We can do a matrix exponentiation in time O(log N) using repeated squaring. So we can find out f(N) as well in O(log N) time as well. As we've to report final answer modulo (10^9 + 7), we would do all operations modulo (10^9 + 7)
/***********************************************CODE*********************************************/
#include<iostream>
using namespace std;
#define mod 1000000007
typedef long long int lli;
void matmult(long long int a[][2],long long int b[][2],long long int c[][2])//multiply matrix a and b. put result in c
{
long long int i,j,k;
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
c[i][j]=0;
for(k=0;k<2;k++)
{
c[i][j]+=(a[i][k]*b[k][j]);
c[i][j]=c[i][j]%mod;
}
}
}
}
void matpow(long long int Z[][2],long long int n,long long int ans[][2])
//find ( Z^n )% M and return result in ans
{
long long int temp[2][2];
//assign ans= the identity matrix initily ans always = identity metrix
ans[0][0]=1;
ans[1][0]=0;
ans[0][1]=0;
ans[1][1]=1;
long long int i,j;
while(n>0)
{
if(n&1)
{
matmult(ans,Z,temp);//z*ans
for(i=0;i<2;i++)
for(j=0;j<2;j++)
ans[i][j]=temp[i][j];
}
matmult(Z,Z,temp);// z*z
for(i=0;i<2;i++)
for(j=0;j<2;j++)
Z[i][j]=temp[i][j];// COPYING RESULT IN Z[][]
n=n/2;
}
return;
}
long long int findFibonacci(long long int n)
{
long long int fib;
long long int Z[2][2]={{2,2},{1,0}},result[2][2];//modify matrix a[][] for other recurrence relations
matpow(Z,n-2,result);
fib=(result[0][0]*3+ result[0][1]*1)%mod; //final multiplication of Z^(n-2) with the initial terms of the series
// IF U SEE THE RECURRENCE THAN U WILL FIND THAT [F[N],F[N-1] ]=Z^N-2 [F[2],F[1]]
// SO F(N)= F[2]*RESULT[0][0]+F[1]*RESULT[0][1]
// ALSO F[2]=3, F[1]=1;;
// cout<<result[0][0]<<" "<<cout<<result[0][1]<<endl;
return fib;
}
int main()
{
int t;
cin>>t;
while(t--)
{
long long int n,m;
cin>>n;
if(n==1 ) cout<<n<<endl;
else if (n==2) cout<<n+1<<endl;
else
{
long long int ll=findFibonacci(n);
cout<<ll<<endl;
}
}
return 0;
}
*******************************************************END*******************************************
ar