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é