đây là một bài toán kinh điển về QHĐ (Quy hoạch động) chữ số và KMP.

Ta gọi ~cnt_{num}~ là số lượng số đẹp trong khoảng từ ~1~ đến ~num~. Như vậy, đáp án của ta với bộ ba ~L~, ~R~, ~k~ sẽ là ~cnt_R - cnt_{L-1}~.

Để tính ~cnt_{num}~, ta gọi gọi ~dp(idx, tightness, suffixMatch, kExist)~ với ý nghĩa là số lượng số đẹp khi:

• Xét qua ~idx~ chữ số đầu tiên, ~len(num)~ - ~idx~ chữ số cuối cùng mỗi chữ số có thể gán giá trị tuỳ thích miễn rằng bạn xét qua những con số nhỏ hơn hoặc bằng ~num~.

• ~tightness = 1~ khi ~idx~ số đầu tiên bằng với ~idx~ chữ số của ~num~, ~tightness = 0~ nếu ~idx~ số đầu tiên nhỏ hơn ~idx~ số đầu tiên của ~num~.

• ~suffixMatch~ chữ số cuối cùng của số đang xét trùng với tiền tố cùng độ dài của số ~k~.

• ~kExist = 1~ khi trong số đang xét đã tồn tại ít nhất một đoạn độ dài ~len(k)~ mà đoạn các chữ số đó tạo thành một số bằng với số ~k~, ~kExist = 0~.

Như vậy, đáp án cho ~cnt_{num} = dp(0, 1, 0, 0)~.

Chi tiết cài đặt bạn có thể tham khảo code ở đây: https://ideone.com/8g51QE