Shafaet's blog

Need help: Uvalive 4332 — Blocks for kids
By Shafaet, 11 years ago, In English

Link

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.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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);
}
→ Reply