Lời giải: Đếm số cách đặt \(N\) con cá trên bàn cờ \(N \times N\)

Tư duy

Đặt \(N\) con cá với điều kiện mỗi hàng có đúng \(1\) con và mỗi cột có đúng \(1\) con. Ta có thể quy về việc chọn hoán vị \(\pi\) của \(\{0, 1, \ldots, N-1\}\), trong đó con cá thứ \(i\) nằm ở cột \(\pi(i)\).

Thuật giải

Đặt dp[mask][c] = số cách đã đặt \(1\) con cá ở mỗi hàng thuộc tập mask (các cột là duy nhất), con cá mới đặt nằm ở cột c và hàng là popcount(mask) - 1.

• Khởi tạo: với hàng \(0\), ta đặt con cá ở mỗi cột c: dp[1 << c][c] = 1.
• Chuyển trạng thái: với mỗi mask, con cá cuối cùng ở cột c. Ta đặt con cá hàng tiếp theo vào cột nextc chưa thuộc mask: dp[mask | (1 << nextc)][nextc] += dp[mask][c].

Đáp án là sum(dp[FULL][c]) – với FULL = (1 << N) - 1.

Đánh giá độ phức tạp

• Thời gian: \(O(N^2 \cdot 2^N)\).
• Bộ nhớ: \(O(N \cdot 2^N)\).

Với \(N \le 8\) ta có \(2^8 = 256\) mask, cực kỳ nhẹ nhàng.

Mã nguồn tham khảo

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n;
    if (!(cin >> n)) return 0;

    int full = (1 << n) - 1;
    vector<vector<long long>> dp(1 << n, vector<long long>(n, 0));
    // Đặt con cá đầu tiên ở mỗi cột
    for (int c = 0; c < n; c++) dp[1 << c][c] = 1;

    for (int mask = 1; mask <= full; mask++) {
        for (int col = 0; col < n; col++) {
            if (!(mask & (1 << col))) continue;
            if (dp[mask][col] == 0) continue;
            for (int nextcol = 0; nextcol < n; nextcol++) {
                if (mask & (1 << nextcol)) continue;
                int nmask = mask | (1 << nextcol);
                dp[nmask][nextcol] += dp[mask][col];
            }
        }
    }

    long long ans = 0;
    for (int c = 0; c < n; c++) ans += dp[full][c];
    cout << ans << "\n";
    return 0;
}