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 bottomup 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(n1, k) + dp(n1, k1) + 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(n1\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(n1) + x\ T(n2) $ 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(n1) \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 code and this code 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\ (nk+1)\ D(i1) + (i2)\ D(i2))/i $ $ D(0)=1 \ and \ D(1)=2\ (nk+1)$ for more information about Matrix exponentiation asked 21 Nov '18, 18:57
