Linear recurrence using Matrix Exponentiation. Check fushar’s blog post
The problem defines the linear recurrence below and we need to find the Nth term.
F = initTax
F[i] = F[i-1] + 1 , for 2 ≤ i ≤ slot1+1
F[i] = F[i-1] x 2 , for slot1+2 ≤ i ≤ slot1+slot2+1
F[i] = F[i-1] x F[i-2] x … x F[i-k] , for i > slot1+slot2+1
Before we proceed with the explanation, lets look at some standard theorems and techniques. This is mainly for beginners. If you are familiar with the headings in this section, you can skip to the Explanation part.
Find an % m for large n
Given positive integers a and large n, we need to find the value of an, and as the result can be huge, its enough to find the result modulo a given integer m . A naive approach is to multiply a to ans = 1, n times. We use a property of modulo ( a * b ) m = ( ( a m ) * ( b m ) m ) and keep all the intermediate values within modulo m. This method takes O(n) time and is very slow for large values of n. There is another popular method using recursive squaring, using the following property.
an = an/2 x an/2 , if n is even
an = an/2 x an/2 x a , if n is odd
If you observe carefully, if we have the answer for an/2 , using just one more step we can find an. This is referred as fast exponentiation by repeated squaring and it runs very fast in O(log n) time. This is valid for not only integers but also when a is a matrix. But the complexity for matrix exponentiation is O(k3 log n), where the matrix is a square matrix of size k x k and each matrix-matrix multiplication takes O(k3) time.
Find ( 1 / a ) % p for prime p
Note that in general, modulo operation doesn’t carry to inner terms for division ( ( a / b ) m != ( ( a m ) / ( b m ) m ) ). It is valid for addition, subtraction and multiplication. We need to use extended euclid method for it, which is a separate topic to study. In special case of prime modulo, there is a simpler method. Using Fermat’s Little Theorem , a(p-1) = 1 (mod p) and dividing both sides by a gives (1/a) (mod p) = a(p-2) (mod p) and using the fast exponentiation method explained above, we can calculate this in O(log n) time.
If you were not successful with this problem, can you solve if we replace the last recurrence involving multiplication to addition ? i.e. the Nth term is the addition of previous k terms ? If yes, then this problem is not much different from it. Suppose we know the value of the first
k terms a1 a2 a3 , … , ak and for all i > k , ai = a(i-1) x a(i-2) x … x a(i-k) and we are asked for find the value of a(n) for some large n. The main idea is, when multiplying powers of same term, the exponents are summed up. Lets consider a simple case of k = 4 and find
the powers of a1 a2 a3 a4 contributed to each ai
So if we know the values of the Nth row in the above table, R[N][1…K], then
a(n) = a1R[N] x a2R[N] x a3R[N] x … x akR[N][k] [Equation 1]
So now the problem is to find the values of the Nth row in the above table, where for each column j, R[n][j] = R[n-1][j] + R[n-2][j] + … + R[n-k][j] [Equation 2]
So if we have the previous k rows of the table R, we can find the next row using the following matrix equation, Rn = A x Rn-1 [Equation 3]
All we need is the matrix A and if in the problem N ≤ slot1 + slot2 + 1 , we can directly find the answer using the two simple recurrences. If N > slot1 + slot2 + 1 , then we find the matrix A(N-(slot1+slot2+1)) and the first row of this matrix has the corresponding powers of the previous k terms. Using Equation 1, we can find the Nth term finally.
Note that in this problem, we need to find the answer % P, where P = 100000007. From fermat’s little theorem, a(P-1) = 1 (mod P) and as we are finding the actual powers of the terms using matrix exponentiation, we should use mod value (P-1) = 100000006 in matrix-matrix multiplications.
This may seem little hard to understand for someone not familiar with solving linear recurrence using matrix exponentiation, so we suggest you to look at the references given first and then attempt this problem.
Can be found here
Can be found here
Both tester’s and setter’s solutions use the same approach as explained above. Try to code the solutions first yourself to know some common mistakes and tricks involved in such problems, before referring the given solutions.
MOD is too heavy
The direct approach using MOD in the inner most loop in matrix-matrix multiplication may take a lot of run time, because MOD is a heavy operation and using it only when needed can make a difference. One simple way is to check, if( x >= MOD ) x %= MOD; Though this may look simple, this can speed up the solution in many cases. For this problem, as MOD is around 108 and matrix size is k = 100 , k * MOD * MOD will still fit in 64-bit signed integer, so we can accumulate the result in innermost loop and take MOD when we come out of it. This can speedup the solution. We didn’t intend to make this strict. Somehow, one of our solutions without this trick was passing within the time limit and we kept time limit as 4s. Ideally, this shouldn’t be such strict. But hey… we all learnt a good lesson and will use MOD wisely next time
thanks to Anton for his comment regarding this below. Please check his comment