Bài gợi ý: Làm đề thi (C.P.VNOI 2021 LMH R3)
Tóm tắt: Đếm số cách chọn \(k\) số nguyên dương phân biệt \(1 \le a_1 < a_2 < \dots < a_k\) sao cho tổng của chúng bằng \(n\), lấy phần dư cho \(10^9 + 7\).

Xét ví dụ nhỏ với \(k = 3\) và \(n = 10\). Ta cần tìm 3 số nguyên dương phân biệt có tổng bằng 10. Ta liệt kê được 4 bộ số thỏa mãn: \((1, 2, 7)\), \((1, 3, 6)\), \((1, 4, 5)\) và \((2, 3, 5)\).

Để dễ đếm hơn, ta khử điều kiện tăng ngặt bằng cách đặt \(a_i = x_i + i\) với \(0 \le x_1 \le x_2 \le \dots \le x_k\). Khi đó, tổng các \(a_i\) trở thành \(\sum x_i + \frac{k(k+1)}{2} = n\). Bài toán chuyển về đếm số nghiệm nguyên không âm của \(x_1 \le x_2 \le \dots \le x_k\) có tổng bằng \(S = n - \frac{k(k+1)}{2}\).

Vì \(n \le 10^9\), ta không thể duyệt qua \(S\) bằng quy hoạch động (DP - kỹ thuật lưu kết quả bài toán con để tính bài toán lớn). Điểm đáng chú ý là \(k \le 10\) rất nhỏ. Số cách phân tích \(S\) thành tổng các phần tử thuộc \(\{1, 2, \dots, k\}\) có hàm sinh với mẫu số là \(\prod_{i=1}^k (1 - x^i)\), tương ứng một đa thức có bậc tối đa \(M = \frac{k(k+1)}{2} \le 55\).

Khi mẫu số có bậc tối đa \(55\), dãy số nghiệm thỏa mãn một hệ thức truy hồi tuyến tính cấp không quá 55. Với \(S \le 10^9\), ta dùng kỹ thuật nhân ma trận trên ma trận chuyển kích thước \(M \times M\) để tính giá trị thứ \(S\) trong thời gian \(O(M^3 \log S)\).

Các bước cài đặt chính cho mỗi test:

• Tính \(S = n - \frac{k(k+1)}{2}\); nếu \(S < 0\) thì in ra \(0\).
• Khai triển đa thức mẫu số \(P(x) = \prod_{i=1}^k (1 - x^i)\) để tìm các hệ số truy hồi.
• Tính trực tiếp các giá trị ban đầu \(dp[0], dp[1], \dots, dp[M-1]\) bằng hai vòng lặp nhỏ.
• Dựng ma trận chuyển kích thước \(M \times M\) rồi tính lũy thừa ma trận bậc \(S\).

Bài tập tương tự:

• Đề thi (THT vòng loại 2020): rèn luyện kỹ năng biến đổi dãy tăng ngặt về bài toán phân tích số và đếm tổ hợp.
• Đếm dãy K phần tử: luyện tư duy chặn cận trạng thái và tối ưu đếm dãy có điều kiện tổng.

Nhân ma trận kết quả sau khi lũy thừa với vector cơ sở ban đầu để lấy giá trị \(dp[S]\) rồi in ra modulo \(10^9 + 7\).