Indian National Olympiad in Informatics (INOI) is round 2 out of 3 (i.e. intermediate) for selection into Indian IOI team.

Problem statement clarification:

Now I get it, I was misinterpreting question all this time. Actually after finish of each round, lead is not the difference between points of that round. But the lead is difference between the points achieved through all rounds including current round - Lakpa Tashi Bhutia

For those of you who haven't solved this problem, this is one of the best problems from which you can learn how limitations of memory and time can make an easy problem, difficult to solve!

Just when I obtained the accepted sign after several trials, I was quite disappointed that I got a worst case running time of 1.98 s . So I headed over to Keshav's github repository and when I tried out the solution posted, it gave me a worst case running time of 0.024 s. Wow! Now that's a huge improvement. I really wanted to upgrade my arsenal with the procedure that had been used, but to my dismay I couldn't understand how it actually works. It would be great if someone posted the technique and procedure employed in solving the problem in the link attached above!

Problem in short: Given a positive integer N, find the number of binary strings of length N which are not periodic. Report the answer modulo M. The non-periodic strings of length 3 are 001, 010, 011, 100, 101, and 110. N <= 150,000.

Indian National Olympiad in Informatics (INOI) is round 2 out of 3 (i.e. intermediate) for selection into Indian IOI team.

Zonal Computing Olympiad is round 1 out of 3 (i.e. beginner) for selection into Indian IOI team.