Editorial for Bedao Regular Contest 13 - 2048
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Nhìn vào bài toán, ta có thể nghĩ ngay tới quy hoạch động chữ số, một trong những thuật toán quy hoạch động cổ điển. Tuy nhiên, vì giới hạn ~n~ tương đối lớn, ta cần tìm cách tối ưu hơn.
Nhận xét quan trọng: Ta thấy được, nếu ~(n\ mod\ 10^{11})~ chia hết cho ~2048~ (hay nói cách khác, ~11~ chữ số cuối cùng của ~n~ chia hết cho ~2048~) thì ~n~ cũng chia hết cho ~2048~ (chứng minh dễ, xin nhường lại cho bạn đọc).
Vì vậy, ta chỉ cần quy hoạch động trên ~11~ chữ số cuối cùng của ~n~, còn các ký tự ~\texttt{?}~ ngoài ~11~ ký tự cuối có thể điền chữ số bất kỳ.
Độ phức tạp: ~O((n - 11) + 11 \cdot 2048)~ = ~O(n)~.
Comments