Hướng dẫn cho Số dư
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:
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\) và \(q = x\) \(mod\) \(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é.
Bình luận