PROBLEM LINKS:DIFFICULTY:SimpleEasy PREREQUISITES:Linear Recurrences, Matrix Exponentiation 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(N1) + f(N2) ) 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:
Let's see why each of these claims hold:
Now we can drop H from the notation to get f(n) = 2 f(n1) + 2 f(n2) with base case of this recurrence as f(1) = 1 and 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:
You can verify that this is nothing but the recurrence we just wrote. Special property of writing it in this form is we [ f(n1) f(n2) ] is exactly of the same form as [ f(n) f(n1) ] and so we can in turn expand it to get:
We can continue expanding term on right handside till we get :
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) SETTER'S SOLUTION:Can be found here. TESTER'S SOLUTION:Can be found here. RELATED PROBLEMS:Codechef Chess Pushing Game REFERENCES:
This question is marked "community wiki".
asked 11 Jul '12, 16:02

Detailed explanation of approach by @alphanso. At first let's define new function Now let's prove the following general recurrence for g(n) = g(k) * g(nk) + 2 * g(k1) * g(nk1), 1 <= k <= n1 The proof will be purely combinatorial. Consider some sequence of coin values 1) Some prefix of our sequence has sum a(1) ... a(j) a(j+1) ... a(L)   sum = k sum = nkBy the product rule and definition of g there are g(k) * g(nk) such sequences.
2) Some prefix has the sum a(1) ... a(j) 2 a(j+2) ... a(L)   sum = k1 sum = nk1(Note that if this prefix is followed by 1 then we are in the first case. Also since each a(j) is either 1 or 2 we can't have any other cases.)
Here the number of sequences is Adding up these two values we get Now choosing And now let's put g(n) = g(1) * g(n1) + 2 * g(0) * g(n2) = 2 * (g(n1) + g(n2)). So we get the recurrence from the editorial. Voilà! answered 25 Sep '12, 21:09

Some of us had to use a onedimensional vector to represent the matrix, because the same approach, when submitted with the matrix represented as a 2x2 vector gave TLE. Could someone provide an explanation for this? answered 11 Jul '12, 18:34
I think that's because you used 3 inner loops for multiplication...
(11 Jul '12, 18:41)
I think I am missing something here. How is that supposed to matter for a matrix of constant size? I did use 3 nested loops (each of the form for(i=0 to 1)) in my first approach, and none in the second, but the operations executed were about the same in both the cases  8 additions and 8 multiplications in the first case, and 4 additions and 8 multiplications in the second one. Can 4 additions (and that too to 0), even if they might have taken place multiple times, affect the running time to such extent?
(11 Jul '12, 19:41)
But that's exactly what you did in your AC solution  removed loops... It was just a tip, because I had similar problem  read here http://discuss.codechef.com/questions/654/digforstevensetterssolutiongottleinpractice
(11 Jul '12, 19:53)

For me the most important thing to realize (about this method) was to know what is the purpose of matrix exponentiation, because I knew how to use it when I had the matrix, but didn't know how to find such matrix. Purpose is simple, when you have few last elements from sequence F_{n} and F_{n1} in this case, you want to generate new one  F_{n+1} and keep the old one F_{n} (for further calculations). So we are looking for some matrix
with property (it says, we want to replace oldest element F_{n1} with new one F_{n+1})  A B  *  F_{n}  =  F_{n+1}   C D   F_{n1}   F_{n}  If you know how matrix multiplication works, 2nd row is simple: C*F_{n} + D*F_{n1} = F_{n} => C = 1, D = 0 If you found the formula for F_{n+1}, 1st row is also simple: A*F_{n} + B*F_{n1} = F_{n+1}, from formula we know that A = 2 and B = 2. Note: matrix I'm using is different from the one in editorial, but it works same way, you just need to know matrix multiplication. answered 17 Jul '12, 19:08

I also did it in O(log N) with a different equation. Y = N  2 f(N) = f(N/2) * f(N  N/2) + f(Y/2) * f(Y  Y/2) http://www.codechef.com/viewsolution/1159064 P.S. I think this equation can be derived from above equation. answered 11 Jul '12, 21:40
in your code, there is calc(N / 2) * calc(N  N / 2) + 2 * calc(Y / 2) * calc(Y  Y / 2) ;)
(12 Jul '12, 14:17)
can u explain this eqn ??? how does it work ???
(25 Sep '12, 15:59)

What would you do if one of the elements of the constructed matrix is negative?? Would u take the mod directly?? Plz reply... answered 05 Sep '12, 12:58

My code gives me tle error whats wrong with my code?? answered 19 Feb '15, 21:14

any good links/resource to know more about matrix exp.?
Here's one they gave in some editorial: http://fusharblog.com/solvinglinearrecurrenceforprogrammingcontest/
@codejack: I tried to describe it a little, you can ask if something is not clear ;)