How to solve - Lockdown Loss | CodeChef?

This is question from recent contest COOK THE CODE:
Cook The Code 2020. The question link is ECODOWN. It is basically a recurrence but not linear so there is no direct way visible to me how to solve it.

F(0) and F(1) are given as p and q respectively. Also the recurrence is:

F(n) = F(n-1)+F(n-2)+F(n-1)F(n-2)

Please share hints on how to approach this question.

f(n) = (p + 1)^{Fib(n - 1)}(q + 1)^{Fib(n)} - 1
Click.
I don’t know how to derive it, but it is a general form of A063896 - OEIS

2 Likes

F(n)+1 = (F(n-1)+1)(F(n-2)+1)

This is the main recursive relation

So our sequence becomes, p, q, pq, pqq, ppqqq, pppqqqqq,…

If you look closely, You’ll see that its p^(Some Fibonacci) x q^(Next Fibonacci).

So the question boils down to finding the Nth Fibonacci quickly. You can use either Matrix Multiplication or any other quick enough method to do that.

NOTE: While calculating the Fibonacci, take Modulo (1e9+6). This is because we will eventually put the Fibonacci numbers in the exponent and X^(M-1) = 1ModM. Something small but can be very dangerous if missed. I was struggling for around an hour because of this.

Solution

2 Likes

I am getting some understanding, but I dont understand the last part, why we need to take fibonacci modulo MOD-1. I mean what goes wrong if I take fibonacci modulo MOD. And say do something like binary_exponentiation(p+1, fib_MOD(n-1), MOD) instead of binary_exponentiation(p+1, fib_MODminus1(n-1), MOD)

I’m claiming that P^{K}modM = P^{Kmod(M-1)}modM

By the Fermat’s little theorem, that I guess you must be aware of, P^{M-1} modM=1.

So we can write

P^{K}modM = P^{q(M-1)+r}modM = P^{(M-1)q}P^{r} modM = P^{r} modM = P^{Kmod(M-1)}modM.

There was a little bit of juggling but I hope that you get the point. Similarly, you can also prove that P^{K}modM \neq P^{KmodM}modM using the same method.

4 Likes

Thanks a lot, makes complete sense. P^{K} \mod {M} may not be written as P^{K \mod M} \mod M because we then get P^{qM+r \mod M} \mod M which is P^{r} \mod M but using Fermat P^{M} \equiv P \mod{M } which gives P^{q+r} \mod{M} which gives different result than P^r \mod M, I hope this is correct thanks!

1 Like