## Editorial for UTS Open '15 #3 - Pogo

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.

Just output .

This one's tricky:

Base cases are all except that . The answer to the problem is .

A diagram would be useful here but I am too lazy to draw one, so I will describe in words what each function represents:

• is the number of ways to satisfy the conditions if you're at the beginning of a line of length , with every tile behind you already visited.
• is similar, but exactly one tile right behind you is unvisited.
• is similar, but exactly two tiles right behind you are unvisited.
• is similar, but in addition to those two tiles, there might be another group of two tiles behind them, and another two, and another two, etc. Also, there might be a group of one tile at the end of that whole chain.
• is similar to , but you can choose whether to start at the first tile or the second.

Complexity: