Hướng dẫn giải của Lát sàn
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu đếm số cách lát sàn nhà kích thước N x M bằng gạch 1x1 (đen hoặc trắng) sao cho trong mỗi hình vuông 2x2 bất kỳ, có ít nhất một viên gạch đen và một viên gạch trắng (tức là không được đồng nhất 4 viên đen hoặc 4 viên trắng). N có thể lên tới $10^{200}$ (rất lớn), trong khi M rất nhỏ (M ≤ 5). Kết quả cần chia lấy dư cho P.
Các cách tiếp cận
Cách Quy hoạch động kết hợp Bignum và Chuyển Ma trận (DP with Big Integer & Matrix Exponentiation)
#include <bits/stdc++.h>
using namespace std;
int M, P;
int maxState;
// Kiểm tra tính hợp lệ giữa 2 cột kề nhau
bool valid(int a, int b) {
for (int i = 0; i < M - 1; ++i) {
int a1 = (a >> i) & 1;
int a2 = (a >> (i + 1)) & 1;
int b1 = (b >> i) & 1;
int b2 = (b >> (i + 1)) & 1;
int sum = a1 + a2 + b1 + b2;
// Nếu 4 ô cùng màu (tổng 0 hoặc 4) thì không hợp lệ
if (sum == 0 || sum == 4) return false;
}
return true;
}
// Nhân 2 ma trận
vector<vector<int>> mul(const vector<vector<int>> &a, const vector<vector<int>> &b) {
vector<vector<int>> res(maxState, vector<int>(maxState));
for (int i = 0; i < maxState; ++i)
for (int k = 0; k < maxState; ++k)
for (int j = 0; j < maxState; ++j)
res[i][j] = (res[i][j] + 1LL * a[i][k] * b[k][j]) % P;
return res;
}
// Lũy thừa ma trận cơ số, số mũ là string (BigInt)
vector<vector<int>> binpow(vector<vector<int>> base, string exp) {
vector<vector<int>> res(maxState, vector<int>(maxState));
for (int i = 0; i < maxState; ++i) res[i][i] = 1;
reverse(exp.begin(), exp.end());
for (char c : exp) {
int digit = c - '0';
for (int k = 0; k < digit; ++k) res = mul(res, base);
base = mul(base, base);
}
return res;
}
int main() {
string N_str;
cin >> N_str >> M >> P;
maxState = 1 << M;
// Xây dựng ma trận chuyển trạng thái (base)
vector<vector<int>> base(maxState, vector<int>(maxState));
for (int i = 0; i < maxState; ++i) {
for (int j = 0; j < maxState; ++j) {
if (valid(i, j)) {
base[i][j] = 1;
}
}
}
// Tính base^(N-1)
// N là string, xử lý lũy thừa
// Logic trừ 1 thủ công cho string
int borrow = 1;
for (int i = N_str.size() - 1; i >= 0; --i) {
int digit = N_str[i] - '0';
if (digit >= borrow) {
N_str[i] = (digit - borrow) + '0';
borrow = 0;
break;
} else {
N_str[i] = (digit - borrow + 10) + '0';
borrow = 1;
}
}
// Xóa số 0 thừa ở đầu
if (N_str[0] == '0' && N_str.length() > 1) N_str.erase(0, 1);
vector<vector<int>> res = binpow(base, N_str);
// Kết quả là tổng tất cả các phần tử của ma trận kết quả
// Hoặc tính sum của vector trạng thái đầu (tất cả đều có thể là đầu)
// Thực tế bài này chỉ cần tổng các cách.
// Khởi đầu: 1 cách cho mỗi cột đầu tiên (tổng là 2^M).
// Sau đó nhân với ma trận (N-1) lần.
// Kết quả là tổng các phần tử của ma trận res * vector [1, 1, ..., 1]
// Tức là tổng các phần tử của ma trận res.
long long ans = 0;
for (int i = 0; i < maxState; ++i)
for (int j = 0; j < maxState; ++j)
ans = (ans + res[i][j]) % P;
// Nếu N=1, ma trận rỗng, phải xử lý riêng
if (N_str == "0") {
// N=1: chỉ cần thỏa mãn điều kiện 2x2 -> không có 2x2 nào => tất cả đều ok
// Tức là 2^M cách.
int total = 1;
for(int i=0; i<M; i++) total = (total * 2) % P;
ans = total;
}
cout << ans << endl;
return 0;
}
- Time Complexity: O((2^M)^3 * log(N)) ~ O(32^3 * len(N))
- Space Complexity: O((2^M)^2) ~ O(1024)
Bài toán có thể coi là một bài đồ thị hoặc quy hoạch động trên các cột. Do M rất nhỏ (≤ 5), số trạng thái của một cột là $2^M$ (tối đa 32). Ta xây dựng ma trận kề $A$ kích thước $2^M \times 2^M$, trong đó $A[i][j] = 1$ nếu cột $i$ và cột $j$ kề nhau mà không vi phạm quy tắc 2x2, ngược lại bằng 0. Số cách lát cho N cột chính là tổng các phần tử của ma trận $A^{N-1}$ (vì có $N-1$ cặp cột kề nhau cho N cột).
Do N rất lớn ($10^{200}$), ta không thể lặp $N$ lần. Tuy nhiên, ta có thể tính lũy thừa ma trận nhanh (O(log N)). Vì N nhập vào là một chuỗi số lớn, ta cần мод hóa quá trình lũy thừa: thực hiện phép nhân ma trận tương ứng với từng chữ số của N (tương tự thuật toán Square and Multiply nhưng adapté cho số mũ dạng string).
Cách Quy hoạch động thông thường (DP Matrix Exponentiation)
// Tương tự Approach 1, nhưng là nền tảng cơ bản
- Time Complexity: O(log N)
- Space Complexity: O(1)
Đây là cách tiếp cận chuẩn cho các bài toán có N lớn và M nhỏ. Phân tích bài toán thành Graph/Cycle. Tuy nhiên, giải pháp này chỉ khả thi khi N có thể fit vào kiểu dữ liệu nguyên chuẩn (long long). Do N trong bài này rất lớn ($10^{200}$), Approach 1 là bắt buộc để xử lý phần đọc input và tính toán số mũ lớn.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O((2^M)^3 * log(N)) ~ O(32^3 * len(N)) | O((2^M)^2) ~ O(1024) | Quy hoạch động kết hợp Bignum và Chuyển Ma trận (DP with Big Integer & Matrix Exponentiation) |
| 2 | O(log N) | O(1) | Quy hoạch động thông thường (DP Matrix Exponentiation) |
Bài học kinh nghiệm
- Mô hình hóa bài toán thành bài toán đếm đường đi trên đồ thị các cột (hoặc ma trận chuyển trạng thái). Do M ≤ 5, số trạng thái cột $2^M = 32$ là rất nhỏ.
- Bài toán quy về tính lũy thừa ma trận $A^{N-1}$. Do N rất lớn ($10^{200}$), cần nhập N dưới dạng string và thực hiện lũy thừa theo từng chữ số (hoặc chia đôi string liên tục).
Lỗi thường gặp
- Xử lý số mũ lớn: Nếu chỉ dùng
long long, $10^{200}$ sẽ tràn bộ nhớ. Phải dùng string hoặc BigInt. - Trường hợp biên N=1: Ma trận lũy thừa $A^0$ là ma trận đơn vị, nhưng logic bài toán với N=1 là $2^M$ cách.
- Lỗi tính toán ma trận: Quên modulo P trong quá trình nhân ma trận.
Bình luận