Trò chơi bắt chước
Xem PDF
Điểm:
400 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Turing hiện đang làm việc để crack các máy bí ẩn. Nhưng ông thấy rằng có hai hàm toán học là \(f(n)\) và \(g(n)\) được sử dụng để mã hóa tin nhắn của người Đức. Ông muốn thử nghiệm khám phá của mình để bắt chước cách mã hóa của máy tính.
Các hàm được định nghĩa là:
- \(g (n + 1) = 4 \times g (n) + f (n + 1) + c\)
- \(f (n + 2) = 3 \times f (n + 1) + 2 * f (n)\)
Dữ liệu ban đầu:
- \(f (0) = 1;\)
- \(f (1) = 1;\)
- \(g (-1) = 1;\)
- \(g (0) = 1;\)
- \(c = 2;\)
Yêu cầu: Cho số nguyên \(n\), cần phải tìm giá trị \(g(n)\mod 10^9+7\).
Input
- Dòng đầu tiên ghi số lượng các trường hợp thử nghiệm \(T\),
- \(T\) dòng tiếp theo mỗi dòng ghi một giá trị của \(n\).
Output
- Với mỗi test \(T\), xuất ra giá trị của \(g(n)\).
Example
Test 1
Input
5
1
2
3
6
1000Output
7
35
159
12835
566998663
Bình luận
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}\) và \(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.
Anh cho em hỏi là làm sao mình suy ra được dòng thứ 3 ạ.
Ý tưởng để xác định được công thức truy hồi theo ma trận như vậy, đó là bạn để ấy, số biến phụ thuộc của từng dãy truy hồi.
Cụ thể như sau: Ở phương trình đầu, ta thấy \(g(n+1)\) phụ thuộc vào \(g(n)\) và \(f(n+1)\) nên ở đây, xét riêng theo hàm \(g\) thì ta thấy \(g(n+1)\) phụ thuộc vào \(g(n)\) do đó chắc chắn sẽ có \(g(n)\) xuất hiện trong công thức truy hồi của ma trận,
Tiếp theo ta xét đến phương trình thứ \(2\), ta để ấy \(f(n+2)\) phụ thuộc vào \(f(n)\) và \(f(n+1)\) nên chắc chắn sẽ có \(f(n),f(n+1)\).
Và cái cuối cùng là hệ số tự do. Vì ở cả hai phương trình đều có, bản chất nó là hàm bậc \(0\) mà thôi nhé
Ps: Những giải thích của mình nó có vẻ hơi không được tự nhiên hoặc nếu có gì sai sót mọi người comment nhé. Ngoài ra, các bạn làm nhiều dạng này thì nó sẽ có cảm giác để tìm ra được cái đó :)). Hy vọng bạn hiểu nhé!
Cảm ơn anh ạ