Hướng dẫn giải của [Beginner Free Contest 19] BWTILE
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
Không có hai ô kề cạnh cùng màu nên việc tô màu phải xen kẽ như bàn cờ. Chỉ có đúng hai cách tô, số ô đen của hai cách là ~(mn+1)/2~ và ~mn/2~ (chia nguyên).
Sub 1: Vét cạn - ~O(2^{mn} \cdot mn)~, dùng khi ~mn \le 20~
Thử mọi cách tô, bỏ cách có hai ô kề cạnh cùng màu, đếm các cách có đúng k ô đen. Trong bộ test không có test nhỏ nên sub1 chỉ đúng 4/10 test khi chạy riêng (các test sai nằm ngoài miền của nó).
Sub 2: Công thức - ~O(1)~
Số cách bằng ~[k = (mn+1)/2] + [k = mn/2]~. Khi mn chẵn hai số hạng bằng nhau nên đáp số là 2. Bẫy: ~mn \le 10^{18}~ nên dùng long long. Đúng 10/10 test.
Chương trình hoàn chỉnh
main đọc m, n, k. Nếu ~mn \le 20~ gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long m, n, k;
// Sub 1: vet can moi cach to mau 2^(m*n), kiem tra khong co 2 o ke canh cung mau, dem cac cach co dung k o den.
// Dung khi m*n <= 20.
void sub1() {
int cells = (int)(m * n);
long long ans = 0;
for (int mask = 0; mask < (1 << cells); mask++) {
bool ok = true;
for (int i = 0; i < m && ok; i++)
for (int j = 0; j < n && ok; j++) {
int id = i * n + j;
int col = (mask >> id) & 1;
if (j + 1 < n && col == ((mask >> (id + 1)) & 1)) ok = false; // o ben phai
if (i + 1 < m && col == ((mask >> (id + n)) & 1)) ok = false; // o ben duoi
}
if (ok && __builtin_popcount(mask) == k) ans++;
}
cout << ans << "\n";
}
// Sub 2: cong thuc. Khong co 2 o ke canh cung mau nen to mau phai la ban co vua (xen ke).
// Chi co 2 cach to: o goc tren trai den (mau den) hoac trang. So o den lan luot la ceil(mn/2) va floor(mn/2).
// Neu mn chan thi ca hai cach cung co mn/2 o den, nen dem 2 cach.
void sub2() {
long long mn = m * n;
long long ans = (k == (mn + 1) / 2) + (k == mn / 2);
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> m >> n >> k;
if (m * n <= 20) sub1();
else sub2();
return 0;
}
Bình luận