tag: dp digit, binary search, dp k-th lexicographical string.

Subtask 1:

Chuẩn bị trước các số Ligma. Độ phức tạp: ~O(k \times log_{10}{(k)})~, với ~k~ là số Ligma thứ ~10^6~.

Subtask 2:

Dễ thấy số Ligma bé thứ ~x~ là số nguyên dương nhỏ nhất thỏa mãn có ít nhất ~x~ số Ligma không lớn hơn nó, vì vậy, ta sẽ sử dụng thuật toán chặt nhị phân (trauma thầy T).

Ta cần giải quyết bài toán: cho một số ~k~, tìm số lượng số Ligma không lớn hơn ~k~. Đây là một bài toán quy hoạch động chữ số kinh điển. Ta sẽ đặt trạng thái như sau: ~dp[digit][sumDigit][sumEvenDigit][sumOddDigit]~, tuy nhiên, ~sumDigit = sumOddDigit + sumEvenDigit~, nên ta có thể lược bỏ chiều ~sumDigit~.

Độ phức tạp: ~O(log_{10}{(x)} ^ 3 \times 81 \times 10)~ với mỗi lần quy hoạch động chữ số, nhân với độ phức tạp ~O(log_2{(x)})~ của chặt nhị phân. Tính ra thì có vẻ lớn, tuy nhiên trên thực tế thuật toán chạy đủ nhanh.

Tài liệu đọc thêm về DP digit

Subtask 3:

Ta sẽ làm tương tự như Sub 2. Tuy nhiên, dễ thấy việc tạo lại bảng DP sau mỗi truy vấn là không cần thiết, mà ta có thể tính trước bảng DP, xong rồi truy vết trên đó để tính nhanh số lượng số Ligma không lớn hơn ~k~. ĐPT: ~O((log_{10}{(x)}) ^ 3 \times 81\times 10)~ cho phần khởi tạo, và ~O(log_2{(x)} \times log_{10}{(x)} \times 10)~ với mỗi truy vấn.

Tài liệu đọc thêm về trick DP digit

Subtask 4:

Đây thực chất chính là bài toán: Tìm dãy có thứ tự từ điển thứ ~k~ thỏa mãn một yêu cầu nào đó. Với những bài toán này, hướng giải chung đều là ta duyệt từ trái qua phải. Với vị trí thứ ~i~, ta thử điền số ~j~ vào, và truy cập bảng DP để xem liệu cách điền vào hậu tố đã vượt quá ~k~ hay chưa.

ĐPT: ~O((log_{10}{(x)}) ^ 3 \times 81\times 10)~ cho phần khởi tạo, và ~O(log_{10}{(x)} \times 10)~ với mỗi truy vấn.

Bài tương tự sử dụng kỹ thuật này