Mình xin chia sẻ lời giải bài này như sau:
Gọi \(len(x)\) là số chữ số của \(x\) và gọi \(F[n]\) là kết quả của bài toán cần tìm.

Khi đó ta có công thức truy hồi sau: \(F[n]=(F[n-1]*10^{len(x)}+x)\text{ % }m=F[n-1]*(10^{len(x)}\text{ % }m)+(x\text{ % }m)\)

Đặt \(p=10^{len(x)}\text{ % }m\) và \(q=x\text{ % }m\)

Khi đó ta có: \(F[n]=p*F[n-1]+q\rightarrow (1)\), trong đó: \(F[1]=q\) và \(p,q\) dễ dàng ta tính được. (Chú ý: Để tính \(p\) ta sử dụng luỹ thừa nhị phân).

Đến đây ta có hai hướng tiếp cận để giải quyết bài toán này:

Cách 1: Dùng nhân ma trận (một thuật toán hữu hiệu trong trường hợp này), và cách giải như sau:

Từ \((1)\implies \begin{pmatrix}F[n-1] & 1 \end{pmatrix}.\begin{pmatrix}p & 0 \\ q & 1\end{pmatrix}=\begin{pmatrix}F[n] & 1 \end{pmatrix}\)

Đặt \(p_n=\begin{pmatrix}F[n] & 1 \end{pmatrix}\) và \(M=\begin{pmatrix}p & 0 \\ q & 1\end{pmatrix}\)

Ta suy ra được: \(p_{n}=p_{n-1} * M=p_{n-2}.M^2=...=p_{1}*M^{n-1}\) trong đó: \(p_1=\begin{pmatrix}q & 1\end{pmatrix}\)

Và đến đây, ta sử dụng tiếp tục sử dụng luỹ thừa nhị phân và phép nhân ma trận để giải quyết bài toán.

Nhưng một điều cần lưu ý trong thực hiện phép nhân ma trận cũng như luỹ thừa nhị phân khi làm đó là để thực hiện phép nhân \(X\text{ x }Y\text{ mod } MOD\), ta cũng nên sử dụng luỹ thừa nhị phân để tránh bị tràn số dẫn đến bị sai kết quả cuối cùng.

Và đây là code của mình cho cách 1: Link

Cách 2: Sử dụng phép biến đổi thông thường, và chúng được thực hiện như sau:

Từ \((1)\implies F[n]=p*F[n-1]+q=p*(p*F[n-2]+q)+q=p^2*F[n-2]+q(1+q)=...\)

\(=p^{n-1} * F[1]+q*(1+p+...+p^{n-2})\)

Hay \(F[n]=p^{n-1} * F[1]+q*(1+p+...+p^{n-2})\)

Đặt \(G(p,n)=1+p+...+p^{n}\). Khi đó \(F[n] = p^{n-1}*q + q*G(p,n-2)\).

Công việc tiếp theo của chúng ta là đi tính \(G(p,n)\), và chúng được thực hiện như sau:

Ta có: \(G(p,n)=\left\{\begin{matrix} 1, \text{ với }n=0 \\ 1+p, \text{ với } n=1 \\ 1 + p*G(p,n-1), \text{ với } n \text{ lẻ } \\(1+p^{\frac{n}{2}})[G(p,\frac{n}{2})-1]+1=(1+p^{\frac{n}{2}})(1+p+...+p^{\frac{n}{2}}-1)+1, \text{ với } n \text{ chẵn }\end{matrix}\right.\)

Và độ phức tạp để tính \(G(p,n)\) là \(O(log(n))\)

Như vậy, bài toán đã được giải quyết xong.

Các bạn có thể tham khảo code cách 2 tại đây: Link

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