Blog: Matrix exponentiation - txhai12 - GTLTOJ: FITHOU Online Judge

Blog: Matrix exponentiation - txhai12

đã đăng vào 2, Tháng 11, 2021, 6:44

Mình đã đọc và làm nhân ma trận lần này là lần thứ 2, mình giải thêm được vài bài mà mình không làm được lần trước, qua quá trình làm bài mình có một vài kiến thức, một vài cái nhìn về Nhân ma trận, mong có thể giúp được các bạn bắt đầu tìm hiểu Nhân ma trận.

Nguồn và tài liệu tham khảo :

VNOI: https://vnoi.info/wiki/algo/trick/matrix-multiplication.md
Hackerearth's note by Mike Koltsov :https://www.hackerearth.com/practice/notes/matrix-exponentiation-1/

Nhân ma trận ?

Bạn nào đã học giải tích 3 hay giải tích và hình đại số, thì có thể sẽ khá quen thuộc.

Là phép nhân giữa hai ma trân, mình sẽ tóm tắt lại, bạn nào đã biết có thể bỏ qua phần này.

Ma trận được kí hiệu như sau : ~A_{n, m}~ với tên ma trận là A, gồm n hàng và m cột

Vd :

~A_{2,4}~ = ~ \begin{bmatrix} 1 & 2 & 3 & 2 \\ 3 & 9 & 5 & 6 \end{bmatrix} ~

Có 1 điều kiện để có thể thực hiện được phép nhân 2 ma trận :

Để có thể nhân được ~A_{n, m}~ với ~B_{p, q}~ thì m = q, hay số "cột của ma trận A" phải bằng "số hàng của ma trận B".
Chú ý nhân ma trận *không có tính chất giao hoán * tức là khi m = q ta có thể thực hiện ~A_{n, m}~ x ~B_{p, q}~ , nhưng không thể thực hiện được ~B_{p, q}~ x ~A_{n, m}~ ,trừ khi q = n.
Tuy nhiên ma trận lại có tính kết hợp tức là ( ~A_{n, m}~ x ~B_{m, p}~ ) x ~B_{p,q}~ = ~A_{n, m}~ x (~B_{m, p}~ x ~B_{p,q}~ ). Chính tính chất rất quan trọng trong bài viết này.

Các nhân hai ma trận

Xét hai ma trận :

Ma trận A có n hàng và k cột : ~A_{n,k}~ .
Ma trận B có k hàng và m cột : ~B_{k,m}~ .

~C_{n,m}~ = ~A_{n,k}~ * ~B_{k,m}~ = ~ \begin{bmatrix} a_{1,1} & a_{1,2} & ... & a_{1,k} \\ a_{2,1} & a_{2,2} & ... & a_{2,k} \\ ... & ... & ... & ... \\ a_{n,1} & a_{n,2} & ... & a_{n,k} \end{bmatrix} ~ * ~ \begin{bmatrix} b_{1,1} & b_{1,2} & ... & b_{1,m} \\ b_{2,1} & b_{2,2} & ... & b_{2,m} \\ ... & ... & ... & ... \\ b_{k,1} & b_{k,2} & ... & b_{k,m} \end{bmatrix} ~ = ~ \begin{bmatrix} c_{1,1} & c_{1,2} & ... & c_{1,m} \\ c_{2,1} & c_{2,2} & ... & c_{2,m} \\ ... & ... & ... & ... \\ c_{n,1} & c_{n,2} & ... & c_{n,m} \end{bmatrix} ~

Ma trận C tích của ma trận A và ma trận B như vậy sẽ có:

n hàng ( số hàng của ma trận A)
m cột ( cột cột của ma trận B)
~C_{i,j}~ = ~ \sum_{ r=1 }^k a_{i,r} * b_{r,j} ~

Một vài tính chất khác :

Ma trận đơn vị ~I_{n}~ là ma trận vuông có n hàng và n cột trong đó, các phần tử tại đường chéo chính bằng 1, còn lại đều bằng 0. ~I_{4}~ = ~ \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} ~
Một ma trận vuông n hàng và n cột nhân với ma trận ~I_{n}~ sẽ bằng chính nó ~C_{n,n}~ * ~I_{n}~ = ~C_{n,n}~.

Minh họa:

~A_{2,4}~ = ~ \begin{bmatrix} 1 & 2 & 3 & 2 \\ 1 & 1 & 1 & 2 \end{bmatrix} ~

~B_{4,3}~ = ~ \begin{bmatrix} 1 & 2 & 2 \\ 1 & 4 & 2 \\ 2 & 1 & 2 \\ 0 & 1 & 1 \end{bmatrix} ~

~A_{2,4}~ * ~B_{4,3}~ = ~ \begin{bmatrix} 1 & 2 & 3 & 2 \\ 1 & 1 & 1 & 2 \end{bmatrix} ~ * ~ \begin{bmatrix} 1 & 2 & 2 \\ 1 & 4 & 2 \\ 2 & 1 & 2 \\ 0 & 1 & 1 \end{bmatrix} ~

~A_{2,4}~ * ~B_{4,3}~ = ~ \begin{bmatrix} 1 & 2 & 3 & 2 \\ 1 & 1 & 1 & 2 \end{bmatrix} ~ * ~ \begin{bmatrix} 1 & 2 & 2 \\ 1 & 4 & 2 \\ 2 & 1 & 2 \\ 0 & 1 & 1 \end{bmatrix} ~ = ~C_{2,3}~ = ~ \begin{bmatrix} 9 & 15 & 13 \\ 4 & 9 & 8 \end{bmatrix} ~

Ta có thể xây dựng code nhân ma trận và đánh giá độ phức tạp khi nhân hai ma trân ~A_{n,k}~ * ~B_{k,m}~ = ~C_{n,m}~ = ~ O(nmk) ~ , vì Ma trận C có m*n phần tử và mỗi phần tử sẽ được tính trong k phép nhân.

#define matrix vector< vector<int> >

matrix mul(matrix a, matrix b){
    int na = (int)a.size();
    int ma = (int)a[0].size();
    int nb = (int)b.size();
    int mb = (int)b[0].size();
    // khởi tạo ma trận kết quả với na dòng và mb cột
    mx res(na, vector<int> mb);

    for(int row_a = 0 ; row_a < na ; row_a++){
        for(int col_b = 0 ; col_b < mb ; col_b++){
            for(int i = 0 ; i < ma ; i++){
                res[row_a][col_b] += a[row_a][i] * b[i][col_b];
            }
        }
    }
    return res;
}

<h7>* Hiểu được cách hoạt động của nhân ma trận là điều quan trọng nhất để có thể làm được các bài toán về nhân ma trận, hãy nắm rõ trước khi đọc phân tiếp theo.</h7>

Cách sử dụng, áp dụng nhân ma trận.

Thông thường một ma trận được xem là "một cách biến đổi" một ma trận thành một ma trận khác theo một quy luật nhất định.

Khi gặp các bài toán mà ta thấy để giải quyết bài toán ta cần thực hiện một hoặc nhiều hoặc rất nhiều "một tập các thao tác biển đổi" lên "một tập giá trị ban đầu" để có thể có được kết quả.

Ta có thể dựng lên một ma trận để tương ứng cho "tập giá trị ban đầu" gọi là A và dựng thêm lên thêm một ma trận để tương ứng cho "một tập các thao tác biến đổi" gọi là COMP, ma trận COMP phải là ma trận vuông, vì ta phải thực hiện liên tục các thao tác, ta sẽ phải duy trì định dạng, chỉ thay đổi trạng thái(giá trị các phần tử) của ma trận A sau mỗi lần nhân, sao cho mỗi lần nhân với ma trận COMP, trạng thái (giá trị) của ma trận A sẽ gần với kết quả hơn.

Để có được kết quả ta chỉ cần dựa vào ma trận kết quả của A * COMP * COMP * ... (n lần), với n là số lần phải thực hiện thao tác để có được kết quả.

Ví dụ : Đề bài yêu cầu tìm số fibonaci thứ n, với n lên tới 10^18. với ~fibo(i) = fibo(i-1) + f(i-2)~

Ta có thể dễ dàng thấy được tập giá trị ban đầu của đề bài này chính là ~fibo(0)~ và ~fibo(1)~
- Ta có ma trận ~A_{1,2}~ = ~ \begin{bmatrix} fibo(0) & fibo(1) \\ \end{bmatrix} ~ = ~ \begin{bmatrix} 0 & 1 \\ \end{bmatrix} ~
Việc cần làm tiếp là xây dựng ma trận để đại diện tương ứng với "tập các thao tác biến đổi".
- Để có thể nhân với ma trận A, ta biết được ma trận vuông COMP sẽ có dạng ~COMP_{2,2}~ = ~ \begin{bmatrix} c_{1,1} & c_{1,2} \\ c_{2,1} & c_{2,2} \end{bmatrix} ~
- Bây giờ chính là lúc vận dụng kiến thức nhân ma trận mà ta có để xác định giá trị cho ma trận ~COMP_{2,2}~.
- Ta mong muốn là từ ~A_{1,2}~ = ~ \begin{bmatrix} fibo(0) & fibo(1) \\ \end{bmatrix} ~ sau khi nhân với ma trận ~COMP_{2,2}~ gần với kết quả hơn,thì trạng thái tiếp theo có thể là ~A_{1,2}~ = ~ \begin{bmatrix} fibo(1) & fibo(2) \\ \end{bmatrix} ~ và điều này là hợp lí và khả thi, vì giá trị của fibo(1) và fibo(2) có thể tính được ra từ fibo(0) và fibo(1) đã và đang có trong ma trận A.
- Gọi ~ANS_{1,2}~ = ~A_{1,2}~ * ~C_{2,2}~ = ~ \begin{bmatrix} fibo(0) & fibo(1) \\ \end{bmatrix} ~ * ~ \begin{bmatrix} c_{1,1} & c_{1,2} \\ c_{2,1} & c_{2,2} \end{bmatrix} ~
- Ta thấy ~ANS[0][0] = fibo(0) * c_{1,1} + fibo(1) * c_{2,1} ~ để ~ANS[0][0]~ đạt giá trị mong muốn, ~fibo(1)~ thì giá trị ~c_{1,1} = 0, c_{2,1} = 1 ~
- Tương tự ta có thể xác định được giá trị ~c_{1,2} = 1, c_{2,2} = 1 ~ để ~ANS[0][1] = fibo(0) + fibo(1) = fibo(2)~

Vậy ma trận ANS cuối cùng để có thể tìm được fibo(n) = ~A_{1,2}~ * (~COMP_{2,2} )^ {n - 1} ~, kết quả bài toán sẽ là ~ANS[0][1]~ = ~fibo(n)~, fibo(1) sau n - 1 lần biến đổi sẽ thành fibo(n).

Với tính chất kết hợp của nhân ma trận ta hoàn toàn có thể tính trước được (~COMP_{2,2} )^ n~ một cách nhanh chóng bằng fastpow hay tính lũy thừa nhanh, giống hệt fastpow với số, chú ý khi ta lấy mũ 0 của một ma trận ta sẽ trả về ma trận ~I_{n}~, với n bằng kích thước của ma trận vuông và ~I_{n}~ có ý nghĩa tương đương với 1 trong hệ cơ số 10, vì ~x^0 = 1~.

#define matrix vector< vector<int> >
// Hàm nhân hai ma trận
matrix mul(matrix a, matrix b){
    int na = (int)a.size();
    int ma = (int)a[0].size();
    int nb = (int)b.size();
    int mb = (int)b[0].size();
    // khởi tạo ma trận kết quả với na dòng và mb cột
    mx res(na, vector<int> mb);

    for(int row_a = 0 ; row_a < na ; row_a++){
        for(int col_b = 0 ; col_b < mb ; col_b++){
            for(int i = 0 ; i < ma ; i++){
                res[row_a][col_b] += a[row_a][i] * b[i][col_b];
            }
        }
    }
    return res;
}
matrix fpow(matrix a, long long n){
    if (n == 0){
        // Trả về ma trạn I(n)
        int na = (int)a.size();
        matrix res(n, vector<int>(n,0));
        for(int i = 0 ; i < na ; i++) res[i][i] =1;// đường chéo chính = 1
        return res;
    }
    //
    auto half = fpow(a,n/2);
    auto res = mul(half,half);
    return (n&1) mul(a,res) : res;
}

Hai kĩ thuật này có tên gọi là "Matrix eponentiation" như 1 trong 2 bài viết mà mình đã đề cập ở đầu bài. Các bài đi với nhân ma trận thường đi kèm chia dư cho mod, khi đó các bạn phải đặt thêm %mod ở một số vị trí trong code ở trên, chúc các bạn may mắn.

Đây chỉ là hướng dẫn về một bài đơn giản và cái nhìn của mình về nhân ma trận, hi vọng nó có thể giúp các bạn đọc dễ dàng hơn trong việc bắt đầu học kĩ thuật này.

Để biết nhiều dạng bài hơn hãy đọc bài này VNOI Nhân ma trận.

Hint cho bài Let's coun ABCD

Tất cả các đuôi có thể, bài này có thể khó cho các bạn ít làm bài toán đếm, đừng ngại đọc tutorial (có trong link nguồn), tại nhiều bài mình phải đọc tutor mới làm dc :'v, có bài đọc tutor phải 2 tiếng ms hiểu ms làm dc(bài Titles ở dưới phần bài tập chẳng hạn).