PROBLEM LINKSDIFFICULTYSIMPLEMEDIUM PREREQUISITESLinear recurrence using Matrix Exponentiation. Check fushar's blog post PROBLEMThe problem defines the linear recurrence below and we need to find the Nth term. @BACKGROUND Find a^{n} % m for large nGiven positive integers a and large n, we need to find the value of a^{n}, 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. a^{n} = a^{n/2} x a^{n/2} , if n is even a^{n} = a^{n/2} x a^{n/2} x a , if n is odd If you observe carefully, if we have the answer for a^{n/2} , using just one more step we can find a^{n}. 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(k^{3} log n), where the matrix is a square matrix of size k x k and each matrixmatrix multiplication takes O(k^{3}) time. Find ( 1 / a ) % p for prime pNote 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^{(p1)} = 1 (mod p) and dividing both sides by a gives (1/a) (mod p) = a^{(p2)} (mod p) and using the fast exponentiation method explained above, we can calculate this in O(log n) time. EXPLANATIONIf 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(i1) x a(i2) x ... x a(ik) 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) = a1^{R[N][1]} x a2^{R[N][2]} x a3^{R[N][3]} x ... x ak^{R[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[n1][j] + R[n2][j] + ... + R[nk][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 Rn1 [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^{(P1)} = 1 (mod P) and as we are finding the actual powers of the terms using matrix exponentiation, we should use mod value (P1) = 100000006 in matrixmatrix 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. SETTER'S SOLUTIONCan be found here TESTER'S SOLUTIONCan be found here APPROACHBoth 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 heavyThe direct approach using MOD in the inner most loop in matrixmatrix 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 10^{8} and matrix size is k = 100 , k * MOD * MOD will still fit in 64bit 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 :) SIMILAR PROBLEM
This question is marked "community wiki".
asked 18 Jun '12, 00:23

It is not mentioned in the editorial that to get AC you need to use hack with skipping modulo operations. Namely, usually some element of the product of matrices int val = 0; for(int k = 0; k < N; ++k) { val = (val + A[i][k] * B[k][j]) % MOD; } But Hence we can use the following much faster code instead: long long val = 0; for(int k = 0; k < N; ++k) { val += A[i][k] * B[k][j]; } val %= MOD; This hack speeds up the program in about 68 times. As for me it was a bad idea to require from the contestants to use this hack. Mostly because of this we have such disbalance between 2nd and 3rd problem of the contest. answered 18 Jun '12, 04:36

@emotionalBlind :
To see this, use Fermat's Little theorem: for a prime P, (a^(p)) % P = (a^1) % P , and (a^(p1)) % P = (a^0) % P . So, notice the cycle length (a^(p+1))% P = (a^2) % P...(a^(p+2))% P = (a^3)%P ....a^(P + P  2)%P = (a^0) % P...a^(P + P  1)%P = (a^1) % P So, the cycle is of "P1", not "P". Thats why we have to use modulo P1. Another way of seeing this: So for any other number number x, write it as x = quotient * (P1) + remainder; (dividing x by P1) now, a^x % P = a^((P1) + (P1) ... + (P1) (quotient times) + remainder) % P. ==> = ((a^(P1)) * (a^(P1)) * ...* (a^(P1)) * (a^remainder)) % P ==> = (a^0 * a^0 * ... * a^0 * (a^remainder)) % P [by doing (a^(P1)) % P, and using Fermats Theorem] ==> = ( a ^ (remainder) ) % P. so, by writing x as x = quotient*(P1) + remainder, what we got above is what we wanted, so, using modulo P1 is correct idea. If we had used, modulo P, we would not get a^x % P = ( a ^ (remainder) ) % P, rather what we get is ( a ^ (quotient + remainder) ) % P, which is correct only if quotient is 0, that is only when x <= P1. answered 18 Jun '12, 07:22
1
what i wanted to say is: To find (a^x)%P, we could just get away by finding (a^remainder)%P. as both are same. (where remainder is found by dividing with P1) And if we found remainder with P, we could not get away like that, rather we will have to find (a^(quotient + remainder))%P, which is also same as (a^x) %P, but we need to know the quotient as well.
(18 Jun '12, 07:39)
1
Thanks, now I understand it clearly.
(18 Jun '12, 09:01)

Two questions: I'm not sure how lyrically managed to solve it using vectors. What's the intuition? The matrix we are trying to power has the property that it's in canonical form. Can we exploit this fact in some way? answered 18 Jun '12, 04:17

((A^n) % M) = (A^(n%phi(M)))%M And for M being Prime phi(M) = M1 answered 18 Jun '12, 19:49

similar problem....http://www.codechef.com/FEB13/problems/CLMBSTRS