Toán học trong lập trình

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\).

Bài gợi ý: CSES - Grid Completion | Hoàn Thành Bảng Số

Tóm tắt: Cho một bảng vuông kích thước \(N \times N\), trên đó một số ô đã điền sẵn chữ A hoặc chữ B. Bạn cần điền thêm vào các ô trống sao cho mỗi hàng và mỗi cột đều có đúng một chữ A và đúng một chữ B, đồng thời không ô nào chứa cả hai chữ. Hãy đếm số cách hoàn thành bảng theo modulo \(10^9 + 7\).

Ta xét một ví dụ nhỏ với \(N = 3\). Giả sử ban đầu ô \((1, 1)\) có chữ A và ô \((2, 2)\) có chữ B. Việc đặt chữ A vào mỗi hàng thực chất là chọn một hoán vị cột \(p\) sao cho \(p_1 = 1\). Đặt chữ B là chọn hoán vị cột \(q\) với \(q_2 = 2\). Điều kiện không ô nào chứa cả hai chữ đồng nghĩa với việc \(p_i \neq q_i\) ở tất cả các hàng \(i = 1, 2, 3\).

Nếu thử chọn từng vị trí rồi kiểm tra xem có ô nào bị trùng không, ta sẽ gặp bế tắc vì các ràng buộc hàng và cột đan xen phức tạp. Với \(N \le 500\), số cách điền tự do có thể lên tới \(500!\), nên không thể thử từng trường hợp. Vậy làm sao để xử lý điều kiện "không có hàng nào bị trùng \(p_i = q_i\)"?

Khi gặp điều kiện "mọi phần tử đều không được vi phạm", hướng đi tự nhiên là dùng nguyên lý bù trừ (inclusion-exclusion). Thay vì chỉ đếm các cách hợp lệ, ta chủ động chọn ra một số hàng cố tình để vi phạm, tức là ép \(p_i = q_i\). Sau khi đã cố định các vị trí vi phạm, các hàng và cột còn lại được ghép tự do bằng các giai thừa.

Để đếm số cách chọn các cặp vi phạm, ta phân loại các hàng và cột thành các nhóm: nhóm chỉ có A, nhóm chỉ có B, và nhóm trống cả hai. Ta dùng quy hoạch động (DP - phương pháp lưu lại kết quả bài toán con để tính bài toán lớn hơn) với mảng dp[i][j] là số cách chọn \(j\) vị trí trùng từ \(i\) hàng trống hoàn toàn. Ở mỗi bước, ta xét hàng thứ \(i\): hoặc không ép trùng, hoặc ghép nó trùng với một trong các cột còn trống.

Khi cài đặt, bạn có thể chia thành các bước rõ ràng:

• Phân loại và đếm số lượng hàng, cột thuộc từng nhóm trạng thái.
• Tính trước mảng giai thừa và tổ hợp theo modulo \(10^9 + 7\).
• Dùng quy hoạch động để đếm số cách tạo ra các điểm trùng nhau giữa A và B.
• Áp dụng công thức bù trừ với dấu \((-1)^k\) nhân với số cách điền tự do của các phần tử còn lại.

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

• Hoán vị không bất động (THTC Vòng Khu vực 2021): Rèn luyện tư duy bù trừ trên bài toán đếm hoán vị không có điểm cố định.
• Giao bài tập: Luyện tập kỹ thuật kết hợp quy hoạch động và bù trừ khi có nhiều điều kiện ràng buộc.

Duyệt số lượng vị trí vi phạm \(k\) từ \(0\) đến \(N\), nhân hệ số đan dấu với số cách điền các vị trí tự do còn lại, rồi cộng dồn vào đáp án theo modulo \(10^9 + 7\).

Bài gợi ý: Câu 3. Hộp quà (HSG 9 - Quảng Trị 2025-2026)

Tóm tắt: Chia dãy \(n\) phần tử thành hai đoạn. Đoạn đầu lấy \(K\) phần tử. Đoạn sau lấy các phần tử còn lại. Tìm \(K\) lớn nhất sao cho ghép được \(K\) cặp thỏa mãn phần tử bên trái nhỏ hơn phần tử bên phải.

Xét ví dụ với 10 hộp quà có giá trị 2 1 4 2 3 2 4 5 2 3. Nếu thử chọn \(K = 4\), ta lấy 4 phần tử đầu là 2 1 4 2 làm hộp thứ nhất. Các phần tử còn lại từ vị trí thứ 5 trở đi làm hộp thứ hai.

Ta cần kiểm tra xem \(K\) phần tử đầu có thể ghép đôi với \(K\) phần tử sau hay không. Mỗi phần tử bên trái phải nhỏ hơn phần tử bên phải được ghép cùng.

Nếu duyệt qua mọi giá trị của \(K\) từ 1 đến \(n\), ta sẽ mất rất nhiều thời gian. Với \(n \le 10^5\), cách kiểm tra trực tiếp từng \(K\) sẽ làm chương trình chạy quá chậm.

Nhận thấy rằng nếu chọn được \(K\) giỏ quà, ta thường cũng ghép được với số lượng nhỏ hơn. Tính chất đơn điệu này cho phép ta dùng chặt nhị phân, là kỹ thuật thu hẹp khoảng tìm kiếm giá trị \(K\) bằng cách chia đôi liên tục.

Để kiểm tra một giá trị \(K\) có hợp lý không, ta áp dụng chiến lược tham lam bằng cách sắp xếp tăng dần các phần tử của cả hai nhóm. Ta ghép phần tử nhỏ nhất của nhóm trái với phần tử nhỏ nhất có thể ở nhóm phải sao cho thỏa mãn điều kiện giá trị.

Trong quá trình cài đặt, ta dùng std::sort để sắp xếp hai đoạn và dùng hai con trỏ để duyệt qua từng phần tử. Khi cần thử một giá trị giữa, gọi hàm check(mid) để đếm số cặp ghép được rồi điều chỉnh biên trái và biên phải.

Bài gợi ý: Hình tròn

Tóm tắt: Nhập vào bán kính \(R\) của một hình tròn, sau đó tính và in ra chu vi cùng diện tích với hằng số \(\pi = 3.14\), làm tròn đến \(1\) chữ số phần thập phân.

Xét ví dụ với bán kính \(R = 1\).

Công thức tính chu vi hình tròn là \(2 \times \pi \times R\) và diện tích là \(\pi \times R^2\).

Với \(R = 1\), chu vi là \(2 \times 3.14 \times 1 = 6.28\) và diện tích là \(3.14 \times 1^2 = 3.14\).

Khi in ra màn hình lấy \(1\) chữ số phần thập phân, giá trị \(6.28\) được làm tròn thành \(6.3\) và \(3.14\) thành \(3.1\).

Cách trực tiếp là lưu giá trị \(R\) vào biến kiểu số thực, rồi áp dụng trực tiếp công thức nhân với \(\pi = 3.14\).

Vì đề bài yêu cầu định dạng kết quả chính xác đúng \(1\) chữ số sau dấu phẩy, thao tác quan trọng là dùng lệnh làm tròn của ngôn ngữ lập trình.

Trong C++, ta gọi cout << fixed << setprecision(1) kết hợp với thư viện iomanip trước khi in giá trị ra màn hình.