Nhân ma trận - Quy hoạch động nhân ma trận

Các bạn thân mến

Nhân ma trận và quy hoạch động nhân ma trận là một trong những chủ đề quan trọng trong lập trình thi đấu, vì vậy hãy cùng mình tìm hiểu chúng nhé

Mục lục

1. Khái niệm về ma trận và nhân ma trận

Ma trận là một bảng chữ nhật gồm các phần tử số, được sắp xếp theo hàng và cột. Kích thước của ma trận thường được kí hiệu là m × n. trong đó m là số hàng, n là số cột

[
A = begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
end{bmatrix}
]

Phép nhân ma trận

Lưu ý phép nhân ma trận chỉ cho phép nhân khi số cột của ma trận A bằng số hàng ma trận B

Phép nhân hai ma trận A (m × p) và B (p × n) cho ra ma trận C (m × n):

C[i,j] = sum(A[i,k] * B[k,j]) for k = 1..p

Phân tích độ phức tạp

Thuật toán thông thường có độ phức tạp là O(mnp). Nếu A và B là ma trận vuông kích thước N, độ phức tạp là O(N³).

Cài đặt nhân ma trận cơ bản trong C++

#include <iostream>
#include <vector>
using namespace std;

vector<vector<long long>> multiplyMatrix(
    const vector<vector<long long>>& A,
    const vector<vector<long long>>& B) 
{
    size_t m = A.size();
    size_t p = A[0].size();
    size_t n = B[0].size();

    vector<vector<long long>> C(m, vector<long long>(n, 0LL));

    for (size_t i = 0; i < m; ++i) {
        for (size_t k = 0; k < p; ++k) {
            long long aik = A[i][k];
            for (size_t j = 0; j < n; ++j) {
                C[i][j] += aik * B[k][j];
            }
        }
    }
    return C;
}

int main() {
    vector<vector<long long>> A = {
        {1, 2, 3},
        {4, 5, 6}
    };
    vector<vector<long long>> B = {
        {7, 8},
        {9, 10},
        {11, 12}
    };

    auto C = multiplyMatrix(A, B);

    cout << "Ma tran C = A * B:n";
    for (auto &row : C) {
        for (auto &val : row)
            cout << val << " ";
        cout << "n";
    }
    return 0;
}

2.Quy hoạch động nhân ma trận

a) Điều kiện áp dụng

1. Khi nhìn thấy giới hạn của N rất lớn (<=10^18) thì chúng ta hoàn toàn có thể áp dụng nhân ma trận
2. Nếu như công thức quy hoạch động rất ổn đỉnh, có tính chất tuyến tính, kiểu như là giá trị của F[n] luôn bằng các phép toán của của 2 hoặc 3 ,… giá trị F trước đó. Ví dụ
  F[n]=F[n-1]+F[n-2] hoặc F[n]=F[n-1]*2+F[n-2]*a[i]

b) Quy hoạch động nhân ma trận trong bài toán tìm số Fibonacci

Trước hết, các bạn có thể xem đề bài ở đây

Oke, các bạnq quan sát nè: Công thức quy hoạch động

F[n]=1*F[n-1]+1*F[n-2]

Nếu các bạn quan sát thì sẽ thấy rằng F[n] được tạo thành khi các bạn nhân 2 vector [1 1]*[F[n-1] F[n-2]]. Hay nói cách khác nếu như có thể xuất hiện phép tính này trong quá trình nhân ma trận thì sẽ tính được F[n].

Mục tiêu quy hoạch đông nhân ma trận là mình có thể setup một công thức duy nhất, và để tính F[n], mình sẽ cần một công thức có dạng

[
begin{pmatrix}
F_3 \[6pt] F_{2}
end{pmatrix}
=
{M}
begin{pmatrix}
F_1 \[4pt] F_2
end{pmatrix}
] [
begin{pmatrix}
F_4 \[6pt] F_{3}
end{pmatrix}
=
{M}
begin{pmatrix}
F_3 \[4pt] F_2
end{pmatrix}
] [
begin{pmatrix}
F_5 \[6pt] F_{4}
end{pmatrix}
=
{M}
begin{pmatrix}
F_4 \[4pt] F_3
end{pmatrix}
]

Từ đó suy ra
[
begin{pmatrix}
F_n \[6pt] F_{n-1}
end{pmatrix}
=
{M}^{n-1}
begin{pmatrix}
F_1 \[4pt] F_0
end{pmatrix}
] Vậy mình cần có
$$M^{n-1}$$

để tính và một ma trận muốn có thể lấy mũ được thì phải là ma trận vuông, đó là vì sao chúng ta làm việc với ma trận
begin{pmatrix}
F_1 \[4pt] F_0
end{pmatrix}
nếu. Và mình sẽ làm việc với ma trận
begin{pmatrix}
F_n \[4pt] F_{n-1}
end{pmatrix}
để có thể có một tính truy hồi tốt.
Vậy làm sao để tìm được ma trận

các bạn quan sát nhé:
[
begin{pmatrix}
F_n \[6pt] F_{n-1}
end{pmatrix}
=
begin{pmatrix}
1*F_{n-1} +1*F_{n-2} \[4pt] 1*F_{n-1}+0*F_{n-2}
end{pmatrix}
=
begin{pmatrix}
1&1 \[4pt] 1&0
end{pmatrix}
*
begin{pmatrix}
F_{n-1} \[6pt] F_{n-2}
end{pmatrix}
]

Và từ đó ta có công thức cuối cùng:

[
begin{pmatrix}
F_n \[6pt] F_{n-1}
end{pmatrix}
=
begin{pmatrix}
1 & 1 \[4pt] 1 & 0
end{pmatrix}^{,n-1}
begin{pmatrix}
F_1 \[4pt] F_0
end{pmatrix}.
]

Để có thể cài đặt Phép mũ của ma trận, ta sẽ sử dụng nhân ấn độ để tiến hành nhân ma trận sau đó tiến hành hoàn thành phép tính để in ra kết quả thôi

Cài đặt


#include 
using namespace std;
#define int long long
const int MOD = 1e9 + 7;

// Function to multiply two 2x2 matrices
void multiplyMatrices(int A[2][2], int B[2][2], int result[2][2]) {
    int temp[2][2];
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            temp[i][j] = 0;
            for (int k = 0; k < 2; ++k) {
                temp[i][j] = (temp[i][j] + 1LL * A[i][k] * B[k][j]) % MOD;
            }
        }
    }
    // Copy temp to result
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) { result[i][j] = temp[i][j]; } } } // Function to compute matrix exponentiation void matrixExponentiation(int base[2][2], int exp, int result[2][2]) { // Initialize result as identity matrix result[0][0] = 1; result[0][1] = 0; result[1][0] = 0; result[1][1] = 1; while (exp > 0) {
        if (exp % 2 == 1) {
            int temp[2][2];
            multiplyMatrices(result, base, temp);
            for (int i = 0; i < 2; ++i) {
                for (int j = 0; j < 2; ++j) {
                    result[i][j] = temp[i][j];
                }
            }
        }
        int temp[2][2];
        multiplyMatrices(base, base, temp);
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) { base[i][j] = temp[i][j]; } } exp /= 2; } } // Function to compute the nth Fibonacci number int fibonacci(int n) { if (n == 0) return 0; if (n == 1) return 1; int base[2][2] = { {1, 1}, {1, 0} }; int result[2][2]; matrixExponentiation(base, n - 1, result); return result[0][0]; } main() { int n; cin >> n;

    cout  << fibonacci(n) << endl;

    return 0;
}

Các bạn có thể làm và nộp tại đây.