Chương trình C++ tìm số lượng ma trận duy nhất có thể tạo ra bằng cách hoán đổi hàng và cột

Mô tả bài toán

Cho ma trận vuông n x n trong đó mỗi phần tử là số nguyên duy nhất từ 1 đến n². Ta có thể thực hiện các phép toán sau theo bất kỳ thứ tự và số lượng nào:

• Chọn hai số nguyên x và y trong ma trận (1 ≤ x < y ≤ n) và hoán đổi hai cột chứa x và y.
• Chọn hai số nguyên x và y trong ma trận (1 ≤ x < y ≤ n) và hoán đổi hai hàng chứa x và y.
• Điều kiện: x + y ≤ k và hai giá trị không được nằm cùng hàng hoặc cùng cột.

Yêu cầu: Tìm số lượng ma trận duy nhất có thể thu được sau các phép toán trên.

Ví dụ

Input: n = 3, k = 15, mat = {{4, 3, 6}, {5, 9, 7}, {1, 2, 8}} → Output: 36.

Ví dụ hoán đổi cột với x=3, y=5 cho ma trận kết quả: 3 4 6 / 9 5 7 / 2 1 8.

Giải thuật

Sử dụng DFS để tìm các thành phần liên thông của hàng và cột thỏa mãn điều kiện tổng ≤ k. Kết quả là tích của giai thừa các kích thước thành phần liên thông (mod 998244353).

Các bước chính:

1. Xây dựng đồ thị hàng (pk) và cột (e): hai hàng/cột được nối nếu tổng các phần tử cùng cột/hàng tương ứng ≤ k.
2. Duyệt DFS trên từng đồ thị để tìm kích thước các thành phần liên thông.
3. Tính giai thừa trước đến 50.
4. Kết quả = (∏ giai thừa(kích thước thành phần hàng)) × (∏ giai thừa(kích thước thành phần cột)) mod 998244353.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;
#define modval 998244353
const int INF = 1e9;

void dfs(int k, vector<int> ver[], bool visited[], stack<int> &s) {
    if (visited[k]) return;
    visited[k] = true;
    s.push(k);
    for (auto j = ver[k].begin(); j != ver[k].end(); ++j)
        dfs(*j, ver, visited, s);
}

void solve(int n, int k, vector<vector<int>> mat) {
    int f[51];
    f[0] = 1;
    for (int i = 1; i <= 50; i++)
        f[i] = (1LL * i * f[i-1]) % modval;

    vector<int> e[n], pk[n];
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            int chk = 0;
            for (int l = 0; l < n; l++)
                if (mat[i][l] + mat[j][l] > k) { chk = 1; break; }
            if (!chk) { pk[i].push_back(j); pk[j].push_back(i); }

            chk = 0;
            for (int l = 0; l < n; l++)
                if (mat[l][i] + mat[l][j] > k) { chk = 1; break; }
            if (!chk) { e[i].push_back(j); e[j].push_back(i); }
        }
    }

    long long resa = 1, resb = 1;
    bool v1[n] = {}, v2[n] = {};

    for (int i = 0; i < n; i++) {
        stack<int> s;
        if (!v1[i]) {
            dfs(i, pk, v1, s);
            if (!s.empty()) resa = resa * f[s.size()] % modval;
        }
    }
    for (int i = 0; i < n; i++) {
        stack<int> s;
        if (!v2[i]) {
            dfs(i, e, v2, s);
            if (!s.empty()) resb = resb * f[s.size()] % modval;
        }
    }
    cout << (resa * resb) % modval;
}

int main() {
    int n = 3, k = 15;
    vector<vector<int>> mat = {{4,3,6},{5,9,7},{1,2,8}};
    solve(n, k, mat);
    return 0;
}

Đầu vào / Đầu ra

Input: 3, 15, {{4, 3, 6}, {5, 9, 7}, {1, 2, 8}}
Output: 36