Mình xin chia sẻ lời giải bài này như sau:

Ta có: \(\left\{\begin{matrix} a_i=b_i (\forall i\le k) \\ a_i =\sum\limits_{j=1}^{k}c_ja_{i-j} (\forall i>k)\end{matrix}\right.\)

\(\implies \begin{pmatrix}a_n & a_{n-1} & ... & a_{n-k+1}\end{pmatrix}.\begin{pmatrix}c_1 & 1 & 0 & ... & 0 \\ c_2 & 0 & 1 & ... & 0 \\ ... \\ c_n & 0 & 0 & ... &0 \end{pmatrix}=\begin{pmatrix}a_{n+1} & a_{n} & ... & a_{n-k+2}\end{pmatrix}\)

Để hiểu tại sao ta lại ra được công thức trên, các bạn cứ lấy các trường hợp nhỏ ứng với \(k=2,k=3,k=4,...\) là ta sẽ rút ra được quy luật.

Đến đây đặt \(p_n = \begin{pmatrix}a_n & a_{n-1} & ... & a_{n-k+1}\end{pmatrix}\) và \(M=\begin{pmatrix}c_1 & 1 & 0 & ... & 0 \\ c_2 & 0 & 1 & ... & 0 \\ ... \\ c_n & 0 & 0 & ... &0 \end{pmatrix}\)

Ta được: \(p_{n} = p_{n-1}.M = ... = p_k.M^{n-k}\)

trong đó: \(p_k=\begin{pmatrix}a_k & a_{k-1} & ... & a_{1}\end{pmatrix}\)

Đến đây, ứng với \(n<k\) thì kết quả rõ ràng là : \(b[n]\). Ngược lại chúng ta sử dụng lũy thừa nhị phân để tính \(p_n\) là xong.

Như vậy là bài toán đã được giải quyết.

Các bạn có thể tham khảo code của mình tại đây