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

Gọi \(F[n]\) là số cách di chuyển đúng khác nhau để đi hết đoạn đường \(n\) mét. Khi đó, ta dễ dàng suy luận ra được \(F[n]=F[n-1]+F[n-2]+F[n-3](\forall n\ge 3)(1)\) với \(F[1]=1,F[2]=2,F[4]=4\) .

Đến đây, ta sử dụng nhân ma trận như sau:

Từ \((1)\implies \begin{pmatrix}F[n-1] & F[n] & F[n+1]\end{pmatrix}.\begin{pmatrix}0 & 0 &1 \\1 & 0 & 1\\0 & 1 &1\end{pmatrix}=\begin{pmatrix}F[n] & F[n+1] & F[n+2]\end{pmatrix}\)

Gọi \(p_n=\begin{pmatrix}F[n] & F[n+1] & F[n+2]\end{pmatrix}\) và \(M=\begin{pmatrix}0 & 0 &1 \\1 & 0 & 1\\0 & 1 &1\end{pmatrix}\).
Ta suy ra được \(p_n=p_{n-1}.M=...=p_1.M^{n-1}\), trong đó: \(p_1=(1,2,4)\)

Đến đây, ta chỉ việc sử dụng luỹ thừa nhị phân và nhân ma trận là xong.

Các bạn có thể tham khảo code tại đây: Link