Tóm tắt đề bài

Cho một mảnh giấy hình vuông kích thước \(2^n \times 2^n\). Thực hiện liên tiếp các bước gấp giấy cho đến khi kích thước còn lại là \(2^k \times 2^k\):

1. Gấp dọc: Mép trái chồng lên mép phải.
2. Gấp ngang: Mép dưới chồng lên mép trên.

Sau khi gấp xong, người ta đục bỏ \(m\) ô tại các vị trí \((i, j)\) trên mảnh giấy đã gấp. Khi mở tờ giấy ra hoàn toàn, hãy đếm số lượng mảnh giấy bị tách rời (các miền liên thông các ô không bị đục bỏ, kề cạnh nhau).

Phân tích

Quy luật mở giấy

Khi ta mở một tờ giấy đã gấp:

• Mở theo chiều dọc: Hình ảnh sẽ được đối xứng qua trục dọc. Các ô ở mép trái của mảnh giấy hiện tại sẽ tiếp xúc với các ô ở mép trái của phần mới mở ra (là bản sao đối xứng).
• Mở theo chiều ngang: Hình ảnh sẽ được đối xứng qua trục ngang. Các ô ở mép dưới của mảnh giấy hiện tại sẽ tiếp xúc với các ô ở mép dưới của phần mới mở ra.

Tính chất liên thông

Một miền liên thông trên mảnh giấy \(2^k \times 2^k\) sau khi mở ra có thể tạo thành một hoặc nhiều mảnh tùy thuộc vào việc nó có chạm vào các cạnh của mảnh giấy hay không:

• Nếu một miền chạm vào cạnh trái, khi mở dọc nó sẽ kết nối với miền đối xứng của chính nó.
• Nếu một miền không chạm vào cạnh nào, mỗi lần mở nó sẽ nhân đôi số lượng mảnh.

Vì quá trình gấp/mở lặp lại \(n-k\) lần, mỗi lần mở bao gồm một bước mở dọc và một bước mở ngang, ta cần tính toán xem sau \(n-k\) lần mở, một miền liên thông ban đầu sẽ sinh ra bao nhiêu mảnh.

Hướng giải quyết

Bước 1: Tìm các miền liên thông ban đầu

Sử dụng thuật toán loang (BFS hoặc DFS) trên lưới \(2^k \times 2^k\) để tìm các miền liên thông của các ô không bị đục bỏ. Với mỗi miền, ta xác định xem nó có chạm vào 4 cạnh của hình vuông \(2^k \times 2^k\) hay không:

• l: Chạm cạnh trái (cột 1)
• r: Chạm cạnh phải (cột \(2^k\))
• u: Chạm cạnh trên (hàng 1)
• d: Chạm cạnh dưới (hàng \(2^k\))

Bước 2: Quy hoạch động đếm số mảnh

Gọi \(f(l, r, u, d, i)\) là số mảnh được tạo ra từ một miền có tính chất \((l, r, u, d)\) sau \(i\) lần mở (mỗi lần mở gồm mở dọc rồi mở ngang).

1. Mở dọc (từ trạng thái \(l, r\)):
   • Nếu \(l=1\) (chạm mép gấp): Miền này dính liền với bản sao của nó qua mép trái. Trạng thái mới về chiều ngang sẽ là \((r, r)\) (vì mép trái đã thành đường ở giữa, hai mép phải ban đầu giờ nằm ở hai phía ngoài cùng).
   • Nếu \(l=0\): Miền này tách rời khỏi bản sao. Ta có 2 miền đối xứng, mỗi miền có trạng thái chiều ngang là \((0, r)\) và \((r, 0)\).
2. Mở ngang (từ trạng thái \(u, d\)):
   Tương tự như mở dọc nhưng áp dụng cho chiều dọc.

Công thức truy hồi tổng quát cho một bước mở (giả sử mở dọc trước, ngang sau):

• Nếu \(l=0\), mở dọc tạo ra 2 phần độc lập. Nếu \(l=1\), mở dọc tạo ra 1 phần duy nhất nhưng tính chất chạm cạnh thay đổi.
• Tương tự với chiều ngang cho \(d=0\) và \(d=1\).

Lưu ý: Trong bài này, thứ tự gấp là Trái \(\to\) Phải, Dưới \(\to\) Trên. Khi mở ra sẽ là Trên \(\to\) Dưới trước, sau đó Phải \(\to\) Trái. Tuy nhiên, do tính chất đối xứng, ta có thể tính toán số mảnh bằng DP dựa trên việc miền đó có chạm vào các "mép gấp" hay không.

Bước 3: Tổng hợp kết quả

Tổng số mảnh bằng tổng các \(f(l, r, u, d, n-k)\) của tất cả các miền liên thông tìm được ở Bước 1.

Độ phức tạp

• Loang: \(O(2^k \times 2^k)\), với \(k \leq 10\) thì \(2^{10} = 1024\), nên chi phí khoảng \(10^6\).
• Quy hoạch động: Số trạng thái là \(2^4 \times (n-k) = 16 \times 30\), rất nhỏ.
• Tổng độ phức tạp: \(O(2^{2k} + n)\), hoàn toàn đáp ứng thời gian cho phép.

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = (1 << 10) + 5;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int n, k, m, h;
int a[N][N];
bool vis[N][N];
int dp[2][2][2][2][35];

int l, r, u, d;

// DFS để tìm miền liên thông và các cạnh mà nó chạm vào
void dfs(int i, int j) {
    if (j == 1) l = 1;
    if (j == h) r = 1;
    if (i == 1) u = 1;
    if (i == h) d = 1;
    vis[i][j] = 1;
    for (int dir = 0; dir < 4; ++dir) {
        int x = i + dx[dir], y = j + dy[dir];
        if (x >= 1 && x <= h && y >= 1 && y <= h && a[x][y] && !vis[x][y]) {
            dfs(x, y);
        }
    }
}

// Hàm DP tính số mảnh sau i bước mở
int calc(int l, int r, int u, int d, int i) {
    if (i == 0) return 1;
    if (dp[l][r][u][d][i] != -1) return dp[l][r][u][d][i];

    int res = 0;
    // Mở dọc (xử lý l) và sau đó mở ngang (xử lý d)
    // Dựa trên cơ chế: nếu không chạm mép gấp (l=0 hoặc d=0) thì số mảnh nhân đôi
    if (d == 0) {
        if (l == 0) {
            // Tách đôi cả dọc lẫn ngang -> 4 phần
            res = calc(l, r, u, d, i - 1) + calc(l, r, d, u, i - 1)

                + calc(r, l, u, d, i - 1) + calc(r, l, d, u, i - 1);
        } else {
            // Chỉ tách đôi theo chiều ngang -> 2 phần
            res = calc(r, r, u, d, i - 1) + calc(r, r, d, u, i - 1);
        }
    } else {
        if (l == 0) {
            // Chỉ tách đôi theo chiều dọc -> 2 phần
            res = calc(l, r, u, u, i - 1) + calc(r, l, u, u, i - 1);
        } else {
            // Không tách phần nào, các phần dính liền nhau
            res = calc(r, r, u, u, i - 1);
        }
    }
    return dp[l][r][u][d][i] = res;
}

void solve() {
    if (!(cin >> n >> k >> m)) return;
    h = (1 << k);

    // Khởi tạo lưới: 1 là giấy, 0 là bị đục
    for (int i = 1; i <= h; ++i)
        for (int j = 1; j <= h; ++j)
            a[i][j] = 1;

    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        a[x][y] = 0;
    }

    memset(dp, -1, sizeof dp);
    memset(vis, 0, sizeof vis);

    int ans = 0;
    for (int i = 1; i <= h; ++i) {
        for (int j = 1; j <= h; ++j) {
            if (a[i][j] && !vis[i][j]) {
                l = r = u = d = 0;
                dfs(i, j);
                // Tính số mảnh sinh ra từ miền liên thông này sau (n-k) lần mở
                ans += calc(l, r, u, d, n - k);
            }
        }
    }
    cout << ans << endl;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    solve();
    return 0;
}