Xây Tháp
Xem PDF
Điểm:
350
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Nguyễn Đình Hải là một thợ xây khét tiếng ở vùng Cao Bằng. Một hôm, ông quyết đinh xây \(n\) tòa tháp để tặng Nguyễn Ngọc Hòa. Hai người này vốn là bạn thân với nhau nhưng do có một số mâu thuẫn đã làm tan nát tình bạn đẹp đẽ này, Hải đã nhận ra lỗi sai của mình nên quyết định xây tháp để tặng Hòa.
- Cách xây tháp :
- Tháp đầu tiên có độ cao là \(a\).
- Kể từ tháp thứ \(2\) trở đi, độ cao của tháp gấp \(2\) lần tháp liền trước và cộng thêm \(b\).
Hãy giúp Hải tính toán xem tháp thứ \(n\) có độ cao bao nhiêu.
- Yêu cầu : Hãy tính xem tháp thứ \(n\) có độ cao là bao nhiêu. Vì kết quả có thể rất lớn nên ghi ra phần chia lấy dữ của kết quả cho \(10^9 + 7\).
Input
- Dòng đầu tiên gồm một số nguyên dương \(T ( T \le 10 )\) là số lần thử nghiệm xây tháp.
- \(T\) dòng tiếp theo là \(3\) số nguyên dương \(a, b, n\).
Output
- Gồm \(T\) dòng, dòng thứ \(k\) là kết quả của lần thử nghiệm thứ \(k\).
Scoring
- Subtask \(1\) (\(60\%\) số điểm): \(a,b,n \le 10^5\).
- Subtask \(2\) (\(20\%\) số điểm): \(a,b,n \le 10^{12}\).
- Subtask \(3\) (\(20\%\) số điểm): \(a,b,n \le 10^{100000}\).
Example
Test 1
Input
3
1 2 3
3 2 1
1 1 2Output
10
3
3
Bình luận
Đề dễ quá mọi người nhỉ 😢
Mình xin chia sẻ lời giải bài này như sau:
Gọi \(u_n\) là độ cao của tháp thứ \(n\). Khi đó ta có công thức truy hồi sau:
\(\left\{\begin{matrix} u_1=a \\ u_n=2*a_{n-1}+b (\text{ }\forall n>1) \end{matrix}\right.\)
Và nhiệm vụ của ta là đi tìm \(u_n\).
Ý tưởng:
Đầu tiên, ta sẽ thực hiện một vài phép biến đổi để khử đi \(b\) ở trong \(u_n=2*u_{n-1}+b(*)\) nhằm đưa về dạng \(v_n=T*v_{n-1}\) với \(T\) là một hằng số nào đó. Để dễ hiểu hơn, chúng ta đi vào chi tiết:
Đặt \(u_n=v_n+ q\) với \(q\) là một hằng số nào đó.
Khi đó ta có: \((*)\iff v_n+q=2*(v_{n-1}+q)+b\iff v_n = 2*v_{n-1}+q+b\)
Để đưa về dạng \(v_n=T*v_{n-1}\) thì \(q+b=0\iff q=-b\)
Lời giải:
Đặt \(u_n=v_{n}-b\)
Khi đó ta có:
\(\left\{\begin{matrix} v_1-b=a \\ v_{n}-b = 2(v_{n-1}-b)+b \end{matrix}\right.\)
\(\iff \left\{\begin{matrix} v_1=a+b \\ v_n=2*v_{n-1} \text{ }(**)\end{matrix}\right.\)
Từ phương trình \((**)\). Ta suy ra được: \(v_n=2*v_{n-1}=2^{2}*v_{n-2}=...=2^{n-1}*v_1\)
Từ đây ta dễ dàng suy ra được: \(v_n=2^{n-1}*(a+b)\implies u_n=2^{n-1}*(a+b)-b(***)\)
Và công việc còn lại của chúng ta là đi tính biểu thức \((***)\)
Chúng ta chú ý rằng, ở subtask cuối, số khá lớn, nên ở đây ta sẽ sử dụng BigNum hoặc Python để giải quyết. Trong bài này, mình sử dụng Python để giải quyết.
Còn phần mod \(10^9+7\). Mình có một chú ý nhỏ là trước khi tính, chúng ta cần tính \(a\text{%}mod\) và \(b\text{%}mod\) trước, và ở đây mình sẽ trình bày phần tính \(2^{n-1}\text{%} mod\) sao cho không bị TLE.
Đặt \(MOD = 10^9+7\)
Áp dụng định lý Fermat bé, ta có: \(2^{MOD-1}\equiv 1(\text{ mod } MOD)\)
Giả sử \(n-1=p*(MOD-1)+q\) (trong đó \(q\) là số dư của \(n-1\) cho \(MOD\)).
Khi đó ta có: \(2^{n-1}=2^{p*(MOD-1)+q} \equiv 2^{q}(\text{ mod } MOD)\)
Đến đây, sử dụng luỹ thừa nhị phân để tính \(2^{q} \text{mod } MOD\) là xong.
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 nhé