Hướng dẫn giải của [Free Contest 04] ROOK1
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Yêu cầu: đếm cách đặt ~K~ quân xe trên bảng ~M \times N~ sao cho không có hai quân cùng hàng hoặc cùng cột, lấy phần dư cho ~1000001~.
Sub 1: Vét cạn đệ quy — ~O(7^{M})~ với ~M, N \le 6~, dùng khi ~M, N \le 6~
Duyệt từng hàng: hàng đó hoặc không đặt quân, hoặc đặt ở một cột chưa dùng. Đếm các cách đặt đúng ~K~ quân.
Nếu chỉ nộp sub này: đúng với các ví dụ trong đề (kiểm tra bằng 1 test mẫu).
Sub 2: Công thức — ~O(K)~
Chọn ~K~ hàng trong ~M~ hàng, chọn ~K~ cột trong ~N~ cột, rồi ghép ~K!~ cách. Modulo ~1000001~ không phải số nguyên tố nên tính ~C(n, k)~ bằng tam giác Pascal, không dùng nghịch đảo.
Nếu chỉ nộp sub này: đúng 1/1 test (mẫu).
Chương trình hoàn chỉnh
Với ~M, N \le 6~ gọi sub 1, còn lại gọi sub 2. Lưu ý: dữ liệu chấm chỉ có 1 test nên độ tin cậy còn hạn chế. Sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
const long long P = 1000001; // modulo đề bài (không phải số nguyên tố, nên không dùng nghịch đảo)
int M, N, K;
long long C[51][101]; // C[n][k] mod P, tính bằng tam giác Pascal
// Sub 1: vét cạn đệ quy theo từng hàng, dùng khi M, N <= 6
// Mỗi hàng hoặc không đặt quân, hoặc đặt ở một cột chưa dùng.
long long dfs(int row, int mask, int placed) {
if (placed > K) return 0;
if (row == M) return placed == K ? 1 : 0;
long long res = dfs(row + 1, mask, placed);
for (int c = 0; c < N; c++)
if (!(mask >> c & 1)) res += dfs(row + 1, mask | (1 << c), placed + 1);
return res;
}
void sub1() { cout << dfs(0, 0, 0) % P << "\n"; }
// Sub 2: công thức — chọn K hàng C(M,K), chọn K cột C(N,K), ghép K! cách
void sub2() {
long long f = 1;
for (int i = 1; i <= K; i++) f = f * i % P;
cout << C[M][K] * C[N][K] % P * f % P << "\n";
}
int main() {
for (int n = 0; n <= 50; n++)
for (int k = 0; k <= 100; k++) C[n][k] = 0;
for (int n = 0; n <= 50; n++) {
C[n][0] = 1;
for (int k = 1; k <= 100; k++)
if (n > 0) C[n][k] = (C[n - 1][k - 1] + C[n - 1][k]) % P;
}
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> M >> N >> K;
if (M <= 6 && N <= 6) sub1();
else sub2();
}
return 0;
}
Bình luận