GROWGOLD - Editorial

flying_ant · June 18, 2012, 12:23am

PROBLEM LINKS

Practice
Contest

DIFFICULTY

SIMPLE-MEDIUM

PREREQUISITES

Linear recurrence using Matrix Exponentiation. Check fushar’s blog post

Fermat’s Little Theorem

PROBLEM

The problem defines the linear recurrence below and we need to find the Nth term.

F[1] = 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

@BACKGROUND
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 aⁿ % m for large n

Given positive integers a and large n, we need to find the value of aⁿ, 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ⁿ = a^n/2 x a^n/2 , if n is even

aⁿ = 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ⁿ. 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³ log n), where the matrix is a square matrix of size k x k and each matrix-matrix multiplication takes O(k³) 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.

EXPLANATION

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

		a1	a2	a3	a4
a1	:	1	0	0	0
a2	:	0	1	0	0
a3	:	0	0	1	0
a4	:	0	0	0	1
---
a5	:	1	1	1	1
a6	:	1	2	2	2
a7	:	2	3	4	4
...

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[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]

										a1	a2	a3	a4
R[n][1]	R[n][2]	R[n][3]	R[n][4]		1	1	1	1		R[n-1][1]	R[n-1][2]	R[n-1][3]	R[n-1][4]
R[n-1][1]	R[n-1][2]	R[n-1][3]	R[n-1][4]	=	1	0	0	0	x	R[n-2][1]	R[n-2][2]	R[n-2][3]	R[n-2][4]
R[n-2][1]	R[n-2][2]	R[n-2][3]	R[n-2][4]		0	1	0	0		R[n-3][1]	R[n-3][2]	R[n-3][3]	R[n-3][4]
R[n-3][1]	R[n-3][2]	R[n-3][3]	R[n-3][4]		0	0	1	0		R[n-4][1]	R[n-4][2]	R[n-4][3]	R[n-4][4]

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.

SETTER’S SOLUTION

Can be found here

TESTER’S SOLUTION

Can be found here

APPROACH

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 10⁸ 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

SIMILAR PROBLEM

HAREJUMP

bcurcio · June 18, 2012, 4:17am

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?

anton_lunyov · June 18, 2012, 4:36am

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 A[N][N] and B[N][N] is computed by the code

int val = 0;
for(int k = 0; k < N; ++k) {
  val = (val + A[i][k] * B[k][j]) % MOD;
}

But % MOD operation here is very slow.
Since MOD is only about 10⁸ then the sum of n products of the form X * Y where X, Y < MOD easily fits in 64bit integer type sine n <= 101.

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 6-8 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 dis-balance between 2nd and 3rd problem of the contest.

emotionalBlind · June 18, 2012, 6:21am

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.

I didn’t understand, how the mod value (P - 1) comes here instead of P as we are calculating A ^ n, for some n. We are not calculating 1 / A or something like that, isn’t it?

mkagenius · June 18, 2012, 6:31am

Actually, ((A^n) % M) != (A^(n%M))%M .

mkagenius · June 18, 2012, 7:22am

@emotionalBlind :

 (a^x) % Mod == (a^(x % (Mod - 1)) % Mod. if Mod is Prime

To see this, use Fermat's Little theorem:
for a prime P, (a^(p)) % P = (a^1) % P  , and (a^(p-1)) % 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 "P-1", not "P".
Thats why we have to use modulo P-1.

Another way of seeing this:
So for any other number number x, write it as x = quotient * (P-1) + remainder; (dividing x by P-1) 
now, a^x % P = a^((P-1) + (P-1) ... + (P-1) (quotient times) + remainder) % P.
==>          = ((a^(P-1)) * (a^(P-1)) * ...* (a^(P-1)) * (a^remainder)) % P
==>          = (a^0 * a^0 * ... * a^0 * (a^remainder)) % P [by doing (a^(P-1)) % P, and using Fermats Theorem]
==>          = ( a ^ (remainder) ) % P.
so, by writing x as  x = quotient*(P-1) + remainder, what we got above is what we wanted,
so, using modulo P-1 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 <= P-1.

mkagenius · June 18, 2012, 7:39am

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 P-1)

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.

emotionalBlind · June 18, 2012, 9:01am

Thanks, now I understand it clearly.

token · June 18, 2012, 6:55pm

I also want to know what is his approach… Cannot understand…

kriateive · June 18, 2012, 7:49pm

((A^n) % M) = (A^(n%phi(M)))%M

And for M being Prime phi(M) = M-1

kriateive · June 18, 2012, 7:49pm