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.

Author: bedao

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

Please read the guidelines before commenting.


There are no comments at the moment.