BBRICKS solution using Matrix Exponentiation

Problem

In this Editorial solve this problem using Matrix Exponentiation and polynomial.
This logic is not mine but I understood by the comment in BBRICKS EDITORIAL (vuvth)

First observation this question can be solve by DP

my first solution for 25 point is using 3 state DP

dp(position, remain, previous\ brick) =dp(n, k, 0/1)

in this equation i can say that
if previous brick is 0 then i can skip this state or i have two chance where to color brick

dp(n, k, 0) = dp(n -1, k , 0 ) + 2\ dp(n - 1, k - 1, 1 )

but if previous brick is 1 then i can skip this state or i have one chance to color brick because I can not color adjacent brick
so

dp(n, k, 1) = dp(n -1, k , 0 ) + dp(n - 1, k - 1, 1 )

for ans is dp(n+1,k,0)

using bottom-up approach we define array dp[2][k][2] and solve.

but after some observation and help of OEIS I found two state dp :-

dp(n,k) = dp(n-1, k) + dp(n-1, k-1) + dp(n -2, k -1) \ \ ... \ \ (1)

if \ (k > n) \ then \ dp(n,k) = 0

it is equation Eq - 1 which help us most in matrix exponentiation

we define polynomial

T(n) = dp(n,n)\ x^n + dp(n, n - 1) \ x^\left(n-1\right) + ...+dp(n,0) x^0

now put Eq - 1 in polynomial Equation you will find new recurrence relation (its really easy to see) you just need pen and paper

T(n) = (x + 1)\ T(n-1) + x\ T(n-2)

so we got Equation which can be use in matrix exponentiation

$
\begin{bmatrix}
\ T(n + 1)\ \ T(n)
\end{bmatrix}

\begin{bmatrix}
\ x + 1 & x\ \
1 &0
\end{bmatrix}
\begin{bmatrix}
\ T(n)\ \ T(n-1)
\end{bmatrix}
$

$
\begin{bmatrix}
\ T(n + 1)\ \ T(n)
\end{bmatrix}

\begin{bmatrix}
\ x + 1 & x\ \
1 &0
\end{bmatrix}^n
\begin{bmatrix}
\ T(1)\ \ T(0)
\end{bmatrix}
$

where \ T(1) = 2x + 1\ and\ T(0) = 1

but for N = 10^9 we can’t make array but here is the good news K <= 1000
only make array for size k+1 we don’t require more

at end we need to find coefficient of x^k to do we just multiply (2x + 1)(x(1,0)) + x(1,1)
and sum of x^k coefficient will be your ans

this is my


(https://www.codechef.com/viewsolution/21669895)
and this 

(https://www.codechef.com/viewsolution/20553858) from where I understood the idea.
Time complexity O ( lgN \ 8 \ k^2 )

some people find ans in O(k) using this equation but i don’t know how it comes so please comment if someone have proof

D(i) = (2\ (n-k+1)\ D(i-1) + (i-2)\ D(i-2))/i

D(0)=1 \ and \ D(1)=2\ (n-k+1)

for more information about Matrix exponentiation

6 Likes

finally , thanks brother.

//