Đây rõ ràng là một bài toán quy hoạch động chữ số kết hợp KMP.

Ta định nghĩa ~\pi_i~ là tiền tố độ dài ~i~ của số ~X~.

Đầu tiên, ta cần tính độ đẹp thật sự của ~\pi_i~, bởi vì trong ~\pi_i~ còn có ~\pi_{kmp_i}~, ~\pi_{kmp_{kmp_i}}, \dots~. Vì vậy, rõ ràng độ đẹp thực sự của ~\pi_i~ là ~v_i + v_{kmp_i} + v_{kmp_{kmp_i}}, \dots~. Ta gọi mảng độ đẹp thực sự đó là mảng ~rv~.

Để chuyển trạng thái dễ dàng, ta xây dựng mảng ~next~ cùng mảng ~kmp~, ta có ~next_{i, c}~ là độ dài hậu tố dài nhất của số (~\pi_i + c~) trùng với tiền tố của số ~X~ (~\pi_i~ là tiền tố độ dài ~i~ của xâu ~X~).

Ta gọi ~cnt_n~ là số số trong đoạn ~[0, n]~ là số xấu. Như vậy, đáp án sẽ là ~cnt_R - cnt_{L - 1}~.

Để tính ~cnt_n~, ta sẽ có trạng thái quy hoạch động ~dp(i, suff, beauty, less\_n)~ là số lượng đẹp thỏa mãn khi:

• Xét qua ~i~ chữ số đầu tiên.

• ~suff~ là độ dài hậu tố dài nhất của số đang xét mà trùng với tiền tố của ~X~.

• ~beauty~ là độ đẹp hiện tại.

• ~less\_n~ là số đang xâu dựng đã nhỏ hơn ~n~ chưa.

Ta chuyển trạng thái như sau: Giả sử ta thêm chữ số ~d~ vào trạng thái ~dp(i, suff, beauty, less\_n)~, khi đó ~suff~ sẽ trở thành ~next_{suff, d}~, ~beauty~ sẽ tăng lên một lượng là ~rv_{next_{suff, d}}~.

Code mẫu: https://ideone.com/OTIzZ2