Phân tích

Đây là một bài toán rất mang tính "toán học", và việc giải quyết nó đòi hỏi tư duy theo các thuật ngữ rất hình thức.

Cách tiếp cận ban đầu

Hãy nghiên cứu quy trình được mô tả trong đề bài. Giả sử thứ hạng của số \(n\) đối với tập \(S\) là \(k\). Vì \(n\) là số lớn nhất trong \(S\), điều đó có nghĩa là số lượng phần tử trong \(S\) là \(k\).

Tiếp theo, hãy xem xét tập \(S' = S \cap \{1, 2, \dots, k\}\). Từ định nghĩa về số thuần khiết, \(k\) bây giờ phải là số thuần khiết đối với \(S'\).

Xây dựng lời giải Quy hoạch động

Liệu điều đó có nghĩa là chúng ta đã giảm được bài toán cho \(n\) xuống một bài toán nhỏ hơn cho \(k\)? Chưa hẳn: giả sử chúng ta biết số lượng các tập \(S'\) khả dĩ mà \(k\) là thuần khiết. Làm thế nào để tìm số lượng các tập \(S\) chứa tập này (và \(n\) là thuần khiết, đồng thời \(S\) có \(k\) phần tử)?

Để làm được điều đó, chúng ta cần biết có bao nhiêu số trong \(S'\). Giả sử có \(k'\) số trong \(S'\). Khi đó, số cách để mở rộng tập \(S'\) này trở lại thành \(S\) chính là số cách chọn \(k - k' - 1\) số từ tập \(\{k+1, k+2, \dots, n-1\}\).

Công thức Quy hoạch động

Hãy định nghĩa \(Count[n, k]\) là số lượng các tập \(S\) là tập con của \(\{2, 3, \dots, n\}\), có \(k\) phần tử, chứa số \(n\) và số \(n\) là thuần khiết trong \(S\).

Lập luận trên chứng minh rằng \(Count[n, k]\) bằng tổng trên tất cả các giá trị \(k'\) của \(Count[k, k']\) nhân với \(C(n-k-1, k-k'-1)\), trong đó \(C(A, B)\) là số cách chọn \(B\) phần tử từ \(A\) phần tử (tổ hợp).

Công thức cụ thể:

Lưu ý: Trường hợp cơ sở là khi \(k=1\), \(Count[n, 1] = 1\) cho mọi \(n > 1\), vì nếu thứ hạng của \(n\) là 1, nó sẽ dẫn thẳng tới số 1 (không nằm trong \(S\)) và thỏa mãn điều kiện.

Độ phức tạp

Chúng ta có thể tính toán các giá trị \(Count\) theo thứ tự tăng dần của \(n\). Điều này sẽ cho chúng ta \(O(n^2)\) giá trị cần tính, mỗi giá trị yêu cầu \(O(n)\) phép tính, dẫn đến tổng thời gian chạy là \(O(n^3)\).

Với \(n=500\) và 100 bộ test, \(O(n^3)\) có vẻ hơi chậm nếu tính lại cho mỗi test. Tuy nhiên, thuật toán trên tính toán câu trả lời cho cả các giá trị \(n\) nhỏ hơn. Điều này có nghĩa là chúng ta chỉ cần chạy nó một lần duy nhất cho \(n=500\), lưu lại kết quả và trả lời cho tất cả các bộ test cùng lúc. Tổng thời gian chạy \(O(n^3)\) (khoảng \(500^3 = 125,000,000\) phép tính, nhưng thực tế ít hơn nhiều do các giới hạn của vòng lặp) là hoàn toàn chấp nhận được trong giới hạn thời gian.

Đừng quên thực hiện tất cả các phép tính theo modulo 100003.

Dựa trên phân tích chính thức của Google Code Jam.