Xếp hình
Xem PDFNguyên rất thích trò chơi xếp tháp. Tòa tháp của Nguyên bao gồm những khối lăng trụ đứng có đáy hình vuông và chiều cao bằng 1. Nguyên sẽ xếp các khối lăng trụ chồng lên nhau để tạo thành một tòa tháp cao.
Mới đây trong lớp học toán, Nguyên được cô giáo dạy về cách tính thể tích các hình khối đơn giản. Nguyên thích thú với kiến thức mới học được và cậu ta muốn tính thể tích tòa tháp của mình.
Tháp của Nguyên bao gồm \(N\) khối lăng trụ đứng chiều cao 1 và có đáy hình vuông và độ dài cạnh đáy từ trên xuống dưới theo thứ tự là \(A_1, A_2, ... A_N.\) Dãy \(A\) được tạo như sau:
- \(A_1 = 1.\)
- \(A_2\) sẽ là một số dương tùy ý mà Nguyên chọn trong mỗi lần chơi để tránh nhàm chán.
- \(A_i (i > 2)\) bằng \(2 × A_2 × A_{i-1}–A_{i-2}\)
Nguyên biết rõ thể tích hình một hình lăng trụ sẽ bằng chiều cao nhân với diện tích đáy nhưng vì ngại tính toán, Nguyên muốn nhờ bạn viết một chương trình giúp cậu ta. Kết quả có thể rất lớn vì vậy bạn chỉ cần ghi ra theo \(\mod M\) với \(M\) là một số nguyên dương cho trước.
Input
- Dòng 1: Ghi số nguyên dương \(K \le 10\) là số bộ dữ liệu.
- \(K\) dòng tiếp: Mỗi dòng ghi 3 số nguyên \(A_2, N, M\) tương ứng với một bộ dữ liệu. (\(1 \le A_2, M \le 10^9, 2\le N \le 10^9\))
Output
- Với mỗi bộ test ghi ra một số duy nhất là kết quả tương ứng trên một dòng.
Example
Test 1
Input
2
1 10 1000
2 3 100 Output
10
54
Bình luận
Mình xin chia sẻ lời giải bài này như sau:
Gọi \(G[n]\) là đáp án cần tìm. Khi đó ta có công thức truy hồi sau:
\(\left\{\begin{matrix}A[n] = 2*A[2]*A[n-1]-A[n-2] (\forall n\ge 3) \\ G[n]=G[n-1]+A[n]^2(\forall n\ge 2)\end{matrix}\right.\), trong đó: \(A[1]=1,A[2]=c,G[1]=1\) với \(c\) được nhập từ test.
Từ đây ta suy ra được:
\(\left\{\begin{matrix}A[n]^2 = 4c*A[n-1]^2-4c*A[n-1]*A[n-2]+A[n-2]^2 \\ A[n]*A[n-1] = 2c*A[n-1]^2-A[n-1]*A[n-2]\\G[n]=G[n-1]+A[n]^2(\forall n\ge 2)\end{matrix}\right.\), trong đó: \(A[1]=1,A[2]=c,G[1]=1\) với \(c\) được nhập từ test.
Nên từ đây, ta suy ra được công thức truy hồi với ma trận như sau:
\(\begin{pmatrix}G[n-2]&F[n-1]^2&F[n-1]*F[n-2]&F[n-2]^2\end{pmatrix}.\begin{pmatrix}1&0&0&0\\1&4c^2&2c&1\\0&-4c&-1&0\\0&1&0&0\end{pmatrix}=\begin{pmatrix}G[n-1]&F[n]^2&F[n]*F[n-1]&F[n-1]^2\end{pmatrix}\)
Tiếp theo, đặt \(p_n=\begin{pmatrix}G[n-1]&F[n]^2&F[n]*F[n-1]&F[n-1]^2\end{pmatrix}\) và \(M=\begin{pmatrix}1&0&0&0\\1&4c^2&2c&1\\0&-4c&-1&0\\0&1&0&0\end{pmatrix}\). Ta được: \(p_{n+1}=p_{n}.M=...=p_2.M^{n-1}\)
Với \(p_2=\begin{pmatrix}1&c^2&c&1\end{pmatrix}\)
Sau khi dùng luỹ thừa nhị phân ta tính được \(p_{n+1}\) ta được \(G[n]\) chính là giá trị cần tìm.
Các bạn có thể tham khảo code tại đây
Ps: Mình nghĩ mấu chốt của những bài như vậy, là ta phải thiết kế được \(p_n\) sao cho có thể tạo được dãy truy hồi với ma trận, và cuối cùng nếu có gì thắc mắc, các bạn cứ comment nhé .
Chú ý: Các bạn cần xử lý mod với số âm để không bị sai kết quả nhé!