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
(Solution: 20553858 | CodeChef) 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