Hướng dẫn cho Số dư


Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: jumptozero

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)\) \(mod\) \(m=F[n-1]*(10^{len(x)}\) \(mod\) \(m)+(x\) \(mod\) \(m)\)

Đặt \(p=10^{len(x)}\) \(mod\) \(m\)\(q = x\) \(mod\) \(m\)

Khi đó ta có: \(F[n]=p*F[n-1]+q\rightarrow (1)\), trong đó: \(F[1]=q\)\(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}\)\(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)\)\(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é.



Bình luận

Không có bình luận nào.