Hướng dẫn cho Trò chơi bắt chước


Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: jumptozero

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

Do \(c=2\) nên ta có:
Ta có: \(\left\{\begin{matrix}g(n+1)=4*g(n)+f(n+1)+2 \\ f(n+2)=3*f(n+1)+2*f(n)\end{matrix}\right.\)

Từ đây ta suy ra được: \(\begin{pmatrix}g(n)&f(n+1)&f(n)&1\end{pmatrix}.\begin{pmatrix}4&0&0&0 \\ 1&3&1&0 \\0&2&0&0 \\2&0&0&1\end{pmatrix}=\begin{pmatrix}g(n+1)&f(n+2)&f(n+1)&1\end{pmatrix}\)

Đặt \(p_n=\begin{pmatrix}g(n)&f(n+1)&f(n)&1\end{pmatrix}\)\(M=\begin{pmatrix}4&0&0&0 \\ 1&3&1&0 \\0&2&0&0 \\2&0&0&1\end{pmatrix}\).

Ta được: \(p_{n}=p_{n-1}.M=p_{n-2}.M^2=...=p_0.M^{n}\), với \(p_0=\begin{pmatrix}1&1&1&1\end{pmatrix}\)

Đến đây sử dụng luỹ thừa nhị phân trên ma trận và phép nhân ma trận, ta đã giải quyết xong bài toán, các bạn có thể tham khảo code tại đây

Ps: Nếu có gì thắc mắc, các bạn cứ comment.



Bình luận

Không có bình luận nào.