Ý tưởng

Một số là số cực đại khi các chữ số thỏa ~d_1 \ge d_2 \ge \cdots \ge d_k~. Tính ~F(X)~ là số lượng số cực đại từ ~1~ đến ~X~ bằng quy hoạch động chữ số với trạng thái vị trí, chữ số trước đó, đã bắt đầu số hay chưa và có bị chặn bởi tiền tố của ~X~ hay không. Đáp án là ~F(b)-F(a-1)~.

Độ phức tạp

~O(16\cdot 10\cdot 2\cdot 2\cdot 10)~ cho mỗi lần tính.