Editorial for DMOPC '14 Contest 5 P6 - Nia and Dominoes

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: FatalEagle

Since $N$ $N$ is really big, we want to find an algorithm that uses $\log N$ $\log N$ , which is just the length of the input (still on the order of $10^8$ $10^{8}$ !). The given sequence is periodic with a maximal period of $M^2$ $M^{2}$ , so we can use a cycle-finding algorithm to find the preperiod and period, and take the input number mod the period, and use some brute force to find the answer for that value.

Time Complexity: $\mathcal{O}(M^2 + \log N)$ $O (M^{2} + \log N)$

Comments

There are no comments at the moment.