### Shafaet's blog

By Shafaet, 7 years ago,

Number of ways to arrange the blocks should be

f(n)=2*f(n-1)+2*f(n-2); //We can fill just one col in two ways or two col in two ways.

But here we need to find: g(n)=f(n)f(0)+f(n-1)f(1)+....+f(0)f(n).

I can find f(n) using matrix expo but can't solve it for g(n).

Thanks for helping.

• +3

 » 7 years ago, # |   +3 Since f(n) only depends on the previous two values f(n-1) and f(n-2), the sequence eventually begins to repeat itself — in this case after only a relatively small number of steps which you can work out using a simple loop.With that in mind, you can take a loop like this which runs in O(N): for (i: 0 -> N) { result += f[i % repeat] * f[(n-i) % repeat]; } ...And since the i-th iteration is the same as the (i % repeat)th iteration, turn it into a loop like this which runs in O(repeat): for (i: 0 -> min(N, repeat - 1)) { result += f[i % repeat] * f[(n-i) % repeat] * (1 + (n-i) / repeat); } 
•  » » 7 years ago, # ^ |   0 Thanks. I got AC using matrix expo.