Hello,

BBRICKS — link

in the editorial for the problem BBRICKS one of the guy posted his solution which uses matrix exponentiation to solve the problem and i couldn't make much from his solution on how to solve the question using matrix exponentiation, so if anyone could please just tell me how this problem can be solved using matrix exponentiation.

solution which uses matrix exponentiation

Even the editorialist has no clue on how to solve it using matrix exponentiation.

Thanks in advance :)

update :- the blog written by abba5 explains the solution of the problem using matrix exponentiation very nicely .

I have the same query!

Auto comment: topic has been updated by shahianshu (previous revision, new revision, compare).Can someone please explain the solution, I am very curious now.

You should start by solving it with

`dp[N][K][state of last two columns]`

. The second dimension denotes the number of bricks already used. Then you remove the first dimension by matrix exponentiation.could you please explain how to remove the first dimension by matrix exponentiation??

Forget about

`[K]`

for a moment (so, now we count all possible ways, not caring about the number of bricks). Then apply the matrix exponentiation just like in computing then-th Fibonacci number.And that

`[K]`

gives us one extra dimension. You can see in the code you linked that it's represented as a vector, and multiplied like a polynomial.Errichto can you please explain what what will be transformation matrix and how to find it? You can probably make a video for the solution and explain it there. DP with matrix exponentiation with multiple dimension is a difficult topic to learn. You can help out many of us.

This can be actually converted into a single dimension dp by the formula:

i*D(i) = 2*(n-k+1)*D(i-1) + (i-2)*D(i-2); D(0)=1 and D(1)=2*(n-k+1)

Compute for i in range 2<=i<=k, answer is D(k) Try yourself for the proof :)

And how is that you arrived at this formula? could you explain the proof.

I wrote my idea in this link. (It's second answers). Sorry for my english.

https://discuss.codechef.com/questions/140916/bbricks-solution-using-matrix-exponentiation May be this will be helpful to you

Hi, when I wrote the editorial, when I came up with the solution for sub task #1, I knew of this solution, using method of generating functions and matrix expo.

It can be solved in

O(2^{3}·k·logk·logN) time using fft using this method, but that would be a huge overkill and UN-necessary info IMO, and hence I did not mention it, since the problem can be solved using basic combinatorical interpretation inO(K) time.Auto comment: topic has been updated by shahianshu (previous revision, new revision, compare).