Cách Nhân Ma Trận – Thông tin tuyển sinh đào tạo Đại học Cao đẳng
Cách Nhân Ma Trận đang là thông tin được nhiều người quan tâm tìm hiểu để lựa chọn theo học sau nhiều đợt giãn cách kéo dài do dịch. Website BzHome sẽ giới thiệu cho bạn những thông tin mới nhất chính xác nhất về Cách Nhân Ma Trận trong bài viết này nhé!
Nội dung chính
Video: Chương 1 Ma trận: Đại số ma trận (phần 1).
Bạn đang xem video Chương 1 Ma trận: Đại số ma trận (phần 1). mới nhất trong danh sách Thông tin tuyển sinh được cập nhật từ kênh Đa dạng TV từ ngày 2022-12-28 với mô tả như dưới đây.
Nhân ma trận (Matrix multiplication)
Thông thường, để đạt được độ phức tạp thuật toán như mong muốn, cách làm thường là tìm ra một thuật toán ban đầu làm cơ sở, rồi từ đó dùng các kỹ năng để giảm độ phức tạp của thuật toán. Trong bài viết này, tôi xin giới thiệu với bạn đọc một kỹ năng khá thông dụng: Nhân ma trận.
Định nghĩa
Ma trận là một mảng chữ nhật gồm các số, ký hiệu, hoặc biểu thức, sắp xếp theo hàng và cột mà mỗi ma trận tuân theo những quy tắc định trước. Các ô trong ma trận được gọi là các phần tử của ma trận. Các phần tử được xác định bằng 2 địa chỉ hàng i và cột j tương ứng (Kí hiệu là aij
).
Ma trận thường được viết trong dấu ngoặc vuông:
Độ lớn hay kích thước của ma trận được định nghĩa bằng số lượng hàng và cột. Một ma trận m hàng và n cột được gọi là ma trận (m×n), trong khi m và n
được gọi là chiều của nó.
- Ví dụ: Ma trận A
là ma trận (3×2)
Ma trận vuông
Ma trận vuông là ma trận có số hàng và số cột bằng nhau. Ma trận (n×n) còn gọi là ma trận vuông cấp n. Các phần tử aii
tạo thành đường chéo chính của ma trận vuông.
- Ví dụ: Ma trận vuông cấp 3
(số hàng và số cột bằng 3)
Ma trận đơn vị (Identity Matrix)
Ma trận đơn vị In cấp n là một ma trận (n×n) trong đó mọi phần tử trên đường chéo chính bằng 1 và tất cả những phần tử khác đều bằng 0. Ma trận đơn vị cấp n cũng chính là ma trận vuông cấp n
.Ví dụ
Vector hàng và vector cột
Vector hàng hay ma trận hàng là một ma trận (1×n), tức là ma trận chỉ gồm một một hàng đơn gồm n
phần tử.
a=[a1 a2 … an]
Vector cột hay ma trận cột là một ma trận (m×1), tức là ma trận chỉ gồm một cột đơn gồm m phần tử.
Phép nhân ma trận
Phép nhân hai ma trận chỉ thực hiện được khi số lượng cột trong ma trận thứ nhất phải bằng số lượng hàng trong ma trận thứ hai. Ma trận kết quả, được gọi là tích ma trận, có số lượng hàng của ma trận đầu tiên và số cột của ma trận thứ hai.
Nếu ma trận A có kích thước (m×n) và ma trận B có kích thước (n×p), thì ma trận tích C=A×B có kích thước (m×p), phần tử đứng ở hàng thứ i, cột thứ j xác định bởi công thức:
Tính chất của phép nhân ma trận
- Tính chất kết hợp: (AB)C=A(BC)
. Tính chất phân phối: (A+B)C=AC+BC, cũng như C(A+B)=CA+CB. Phép nhân ma trận không có tính chất giao hoán: Tích AB có thể xác định trong khi BA không nhất thiết phải xác định, tức là nếu A và B lần lượt có số chiều (m×n) và (n×p), và m≠p. Thậm chí khi cả hai tích này đều tồn tại thì chúng không nhất thiết phải bằng nhau, tức là AB≠BA.
- Ví dụ:
Khi thực hiện nhân một ma trận bất kì với ma trận đơn vị thì vẫn thu được kết quả của chính ma trận đó, tức là: AIn=ImA=A (với ma trận A kích thước (m×n) bất kỳ). Cũng chính vì tính chất này mà I có tên gọi là ma trận đơn vị.
Lũy thừa ma trận
Cho ma trận vuông A cấp n. Khi đó ta có phép tính ma trận A lũy thừa k (kí hiệu: Ak), với k là một số nguyên không âm.
Nhờ tính chất kết hợp của phép nhân ma trận nên ta có thể tính nhanh lũy thừa của ma trận tương tự như cách tính hàm mũ thông thường bằng phương pháp chia để trị (tính ak với a là số nguyên).
Cài đặt
Lưu ý: Khác với định nghĩa bên trên, trong cách cài đặt sau, các hàng và cột của ma trận được đánh số bắt đầu từ 0 để thuận tiện cho việc xử lí.
#include <bits/stdc++.h>
using namespace std;
using type = int; // Kiểu dữ liệu các phần tử của ma trận
struct Matrix {
vector <vector <type> > data;
// Số lượng hàng của ma trận
int row() const { return data.size(); }
// Số lượng hàng của ma trận
int col() const { return data[0].size(); }
auto & operator [] (int i) { return data[i]; }
const auto & operator[] (int i) const { return data[i]; }
Matrix() = default;
Matrix(int r, int c): data(r, vector <type> (c)) { }
Matrix(const vector <vector <type> > &d): data(d) {
// Kiểm tra các hàng có cùng size không và size có lớn hơn 0 hay không
// Tuy nhiên không thực sự cần thiết, ta có thể bỏ các dòng /**/ đi
/**/ assert(d.size());
/**/ int size = d[0].size();
/**/ assert(size);
/**/ for (auto x : d) assert(x.size() == size);
}
// In ra ma trận.
friend ostream & operator << (ostream &out, const Matrix &d) {
for (auto x : d.data) {
for (auto y : x) out << y << ' ';
out << 'n';
}
return out;
}
// Ma trận đơn vị
static Matrix identity(long long n) {
Matrix a = Matrix(n, n);
while (n--) a[n][n] = 1;
return a;
}
// Nhân ma trận
Matrix operator * (const Matrix &b) {
Matrix a = *this;
// Kiểm tra điều kiện nhân ma trận
assert(a.col() == b.row());
Matrix c(a.row(), b.col());
for (int i = 0; i < a.row(); ++i)
for (int j = 0; j < b.col(); ++j)
for (int k = 0; k < a.col(); ++k)
c[i][j] += a[i][k] * b[k][j];
return c;
}
// Lũy thừa ma trận
Matrix pow(long long exp) {
// Kiểm tra điều kiện lũy thừa ma trận (là ma trận vuông)
assert(row() == col());
Matrix base = *this, ans = identity(row());
for (; exp > 0; exp >>= 1, base = base * base)
if (exp & 1) ans = ans * base;
return ans;
}
};
int main(){
Matrix a({
{1, 2},
{3, 4}
});
Matrix b({
{0, 10, 100},
{1, 1, 10}
});
cout << a * b << 'n';
// 2 12 120
// 4 34 340
cout << a.pow(3) << 'n';
// 37 54
// 81 118
b = a;
cout << b << 'n';
// 1 2
// 3 4
b = Matrix::identity(3);
cout << b << 'n';
// 1 0 0
// 0 1 0
// 0 0 1
b = Matrix(2, 3);
cout << b << 'n';
// 0 0 0
// 0 0 0
Matrix c(3, 2);
cout << c << 'n';
// 0 0
// 0 0
// 0 0
}Đánh giá
Ngoài cách cài đặt tính lũy thừa ma trên như trên thì ta còn có thể cài đặt theo một cách khác bằng đệ quy như sau:
Matrix pow(long long exp) {
Matrix base = *this;
if (exp == 0) return identity(base.row());
if (exp == 1) return base;
Matrix p = pow(exp >> 1);
p = p * p;
if (exp & 1) return p * base;
return p;
}Độ phức tạp
Ví dụ 1
Chúng ta hãy cùng xem xét một ví dụ kinh điển nhất trong ứng dụng của phép nhân ma trận.
Bài toán
Cho một hình chữ nhật kích thước 2×N (1≤N≤109). Hãy đếm số cách lát các viên gạch nhỏ kích thước 1×2 và 2×1 vào hình trên sao cho không có phần nào của các viên gạch nhỏ thừa ra ngoài, cũng không có vùng diện tích nào của hình chữ nhật không được lát.
Phân tích
Gọi Fi là số cách lát các viên gạch nhỏ vào hình chữ nhật kích thước 2×i
. Ta có:
- Nếu sử dụng viên gạch kích thước 1×2
thì Fi=Fi−2. Nếu sử dụng viên gạch kích thước 2×1 thì Fi=Fi−1
- .
⇒Fi=Fi−1+Fi−2.
Hiển nhiên cách làm thông thường là tính lần lượt các Fi. Tuy nhiên, cách làm này hoàn toàn không hiệu quả với N lên đến 109
, và ta cần một cách tiếp cận khác.
Ta xét các lớp số:
Ta hình dung mỗi lớp là một ma trận (2×1). Tiếp đó, ta sẽ biến đổi từ lớp i−1 đến lớp i. Sau mỗi lần biến đổi như vậy, ta tính thêm được một giá trị Fi. Để thực hiện phép biến đổi này, chú ý là các số ở lớp sau chỉ phụ thuộc vào lớp ngay trước nó theo các phép cộng, ta tìm được cách biến đổi bằng nhân ma trận:
Vậy bài toán trên được đưa về dạng nhân ma trận. FN được tính dựa vào phép lũy thừa của ma trận A
.Cài đặt
Lưu ý: Khác với định nghĩa bên trên. Trong cách cài đặt sau, các hàng và cột của ma trận được đánh số bắt đầu từ 0
để thuận tiện cho việc xử lí.
#include <bits/stdc++.h>
using namespace std;
const int mod = 111539786;
using type = int;
struct Matrix {
vector <vector <type> > data;
int row() const { return data.size(); }
int col() const { return data[0].size(); }
auto & operator [] (int i) { return data[i]; }
const auto & operator[] (int i) const { return data[i]; }
Matrix() = default;
Matrix(int r, int c): data(r, vector <type> (c)) { }
Matrix(const vector <vector <type> > &d): data(d) { }
friend ostream & operator << (ostream &out, const Matrix &d) {
for (auto x : d.data) {
for (auto y : x) out << y << ' ';
out << 'n';
}
return out;
}
static Matrix identity(long long n) {
Matrix a = Matrix(n, n);
while (n--) a[n][n] = 1;
return a;
}
Matrix operator * (const Matrix &b) {
Matrix a = *this;
assert(a.col() == b.row());
Matrix c(a.row(), b.col());
for (int i = 0; i < a.row(); ++i)
for (int j = 0; j < b.col(); ++j)
for (int k = 0; k < a.col(); ++k){
c[i][j] += 1ll * a[i][k] % mod * (b[k][j] % mod) % mod;
c[i][j] %= mod;
}
return c;
}
Matrix pow(long long exp) {
assert(row() == col());
Matrix base = *this, ans = identity(row());
for (; exp > 0; exp >>= 1, base = base * base)
if (exp & 1) ans = ans * base;
return ans;
}
};
int main(){
Matrix a({
{1, 1},
{1, 0}
});
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
Matrix tmp = a.pow(n - 1);
cout << (tmp[0][0] + tmp[0][1]) % mod << 'n';
}
}Đánh giá
Độ phức tạp
Độ phức tạp của thuật toán là O(T×23×logN). Với T là số lượng bộ test.
Ví dụ 2
Bây giờ chúng ta sẽ cùng xem xét một ví dụ tổng quát hơn của ví dụ 1.
Bài toán
Cài đặt
Lưu ý: Khác với định nghĩa bên trên. Trong cách cài đặt sau, các hàng và cột của ma trận được đánh số bắt đầu từ 0 để thuận tiện cho việc xử lí.
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9;
using type = int;
struct Matrix {
vector <vector <type> > data;
int row() const { return data.size(); }
int col() const { return data[0].size(); }
auto & operator [] (int i) { return data[i]; }
const auto & operator[] (int i) const { return data[i]; }
Matrix() = default;
Matrix(int r, int c): data(r, vector <type> (c)) { }
Matrix(const vector <vector <type> > &d): data(d) { }
friend ostream & operator << (ostream &out, const Matrix &d) {
for (auto x : d.data) {
for (auto y : x) out << y << ' ';
out << 'n';
}
return out;
}
static Matrix identity(long long n) {
Matrix a = Matrix(n, n);
while (n--) a[n][n] = 1;
return a;
}
Matrix operator * (const Matrix &b) {
Matrix a = *this;
assert(a.col() == b.row());
Matrix c(a.row(), b.col());
for (int i = 0; i < a.row(); ++i)
for (int j = 0; j < b.col(); ++j)
for (int k = 0; k < a.col(); ++k){
c[i][j] += 1ll * a[i][k] % mod * (b[k][j] % mod) % mod;
c[i][j] %= mod;
}
return c;
}
Matrix pow(long long exp) {
assert(row() == col());
Matrix base = *this, ans = identity(row());
for (; exp > 0; exp >>= 1, base = base * base)
if (exp & 1) ans = ans * base;
return ans;
}
};
int b[15], c[15];
int main(){
int t;
cin >> t;
while (t--) {
int n, k;
cin >> k;
for (int i = 1; i <= k; ++i) cin >> b[i];
for (int i = 1; i <= k; ++i) cin >> c[i];
cin >> n;
if (n <= k) { cout << b[n] << 'n'; continue; }
// Xây dựng ma trận cơ sở
Matrix base(k, 1);
for (int i = 1; i <= k; ++i) base[i - 1][0] = b[i];
// Xây dựng ma trận hệ số D
Matrix d(k, k);
for (int i = 0; i < k - 1; ++i) d[i][i + 1] = 1;
for (int i = 0; i < k; ++i) d[k - 1][i] = c[k - i];
Matrix ans = d.pow(n - k) * base;
cout << ans[k - 1][0] << 'n';
}
}Đánh giá
Độ phức tạp
Độ phức tạp của thuật toán là O(t×k3×log(n−k)). Với t là số lượng bộ test.
Ví dụ 3
Bài toán
Người ta mới tìm ra một loại vi khuẩn mới. Chúng sống thành N bầy (N≤100), đánh số từ 0 đến N−1. Ban đầu, mỗi bầy này chỉ có một con vi khuẩn. Tuy nhiên, mỗi giây, số lượng vi khuẩn trong các bầy lại có sự thay đổi: Một số vi khuẩn có thể chết đi, sinh sản thêm, hoặc di chuyển sang bầy khác. Những thay đổi này luôn tuân theo một quy luật có sẵn. Tại mỗi giây chỉ xảy ra đúng một quy luật. Các quy luật này được thực hiện nối tiếp nhau và theo chu kỳ. Có nghĩa là, nếu đánh số các quy luật từ 0 đến M−1, tại giây thứ S thì quy luật được áp dụng sẽ là (S−1)modM (M≤1000)
.Nhiệm vụ của bạn là tìm xem, với một bộ các quy luật cho trước, sau T đơn vị thời gian (T≤1018), mỗi bầy có bao nhiêu vi khuẩn.
Các loại quy luật có thể có:
Phân tích
Cách làm đơn giản nhất là chúng ta mô phỏng lại số lượng vi khuẩn trong mỗi bầy qua từng đơn vị thời gian. Cách làm này có độ phức tạp O(T×N×k) với O(k) là độ phức tạp cho xử lý số lớn. Cách này không thể chạy được với T
lớn.
Ta hình dung số lượng vi khuẩn trong mỗi bầy trong một đơn vị thời gian là một dãy số. Như vậy, mỗi quy luật cho trước thực chất là một phép biến đổi từ một dãy số thành một dãy số mới, và ta hoàn toàn có thể thực hiện biến đổi này bằng một phép nhân ma trận.
Cụ thể hơn, ta coi số lượng vi khuẩn trong N bầy tại một thời điểm xác định là một ma trận 1×N, và mỗi phép biến đổi là một ma trận N×N
. Khi áp dụng mỗi phép biến đổi, ta nhân hai ma trận nói trên với nhau.
Bây giờ, xét trường hợp N=4, các ma trận tương ứng với các phép biến đổi lần lượt được mô tả như sau:
-
Biến đổi:
A 2 01 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 -
Biến đổi:
B 2 61 0 0 0 0 1 0 0 0 0 6 0 0 0 0 1 -
Biến đổi:
C 1 31 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 -
Biến đổi:
D 1 31 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 -
Biến đổi:
E 1 31 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 -
Biến đổi:
F 0 00 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0
Cũng như các bài toán trước, ta sẽ cố gắng áp dụng việc tính toán lũy thừa, kết hợp với phép nhân ma trận để giảm độ phức tạp từ T xuống logT
. Tuy nhiên, có thể thấy việc sử dụng phép lũy thừa trong bài toán này phần nào phức tạp hơn bởi các ma trận được cho không giống nhau. Để giải quyết vấn đề này, ta làm như sau:
Gọi X1,X2,…,Xm
là các ma trận tương ứng với các phép biến đổi được cho.
Đặt X=X1×X2×…×Xm
.
Đặt S=[1,1,…,1]
(dãy số lượng vi khuẩn tại thời điểm đầu tiên).
Như vậy, Y=S×Xt×X1×X2×…×Xr là ma trận thể hiện số lượng vi khuẩn tại thời điểm M×t+r
.
Như vậy, thuật toán đến đây đã rõ. Ta phân tích T=M×t+r, nhờ đó, ta có thể giải quyết bài toán trong O(N3×M) cho bước tính ma trận X và O(N3×(logT/M+M)) cho bước tính Y. Bài toán được giải quyết.
Ví dụ 4
Bài toán
Số đẹp là một số nguyên dương với bất kỳ chữ số lẻ nào (1,3,5,7,9) đều xuất hiện lẻ lần nếu nó xuất hiện và bất kỳ chữ số chẵn nào (0,2,4,6,8) cũng xuấn hiện chẵn lần nếu nó xuất hiện. Ví dụ số 141222124 là một số đẹp. Gọi fn là số lượng số đẹp có không quá n chữ số. Yêu cầu với một số n (1≤n≤1018) tính fnmod1000000123.
Phân tích
Cách làm đơn giản nhất là ta sử dụng quy hoạch động với 4 trạng thái:
Ta không phải lưu số chữ số chẵn đã xuất hiện vì nếu chữ số chẵn đó không xuất hiện thì cũng đã được tính vào trường hợp nó đã xuất hiện chẵn lần rồi.
Do đó, ta có công thức quy hoạch động theo như code sau:
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 123;
int n;
int dp[10005][6][6][6];
long long digit_dp(int added, int ewoc, int owoc, int added_odd) {
// Khi đã chọn đủ n chữ số
if (added == n) return (!ewoc && owoc == added_odd);
if (dp[added][ewoc][owoc][added_odd] != -1) return dp[added][ewoc][owoc][added_odd];
long long cur = 0;
// Thêm vào 1 số chẵn đã xuất hiện lẻ lần
if (ewoc)
cur += digit_dp(added + 1, ewoc - 1, owoc, added_odd) * ewoc;
// Thêm vào 1 số chẵn đã xuất hiện chẵn lần
if (ewoc < 5)
cur += digit_dp(added + 1, ewoc + 1, owoc, added_odd) * (5 - ewoc);
// Thêm vào 1 số lẻ chưa xuất hiện
if (added_odd < 5)
cur += digit_dp(added + 1, ewoc, owoc + 1, added_odd + 1) * (5 - added_odd);
// Thêm vào 1 số lẻ đã xuất hiện lẻ lần
if (owoc)
cur += digit_dp(added + 1, ewoc, owoc - 1, added_odd) * owoc;
// Thêm vào 1 số lẻ đã xuất hiện chẵn lần
if (owoc < added_odd)
cur += digit_dp(added + 1, ewoc, owoc + 1, added_odd) * (added_odd - owoc);
// Không nhất thiết phải chọn đủ n chữ số
if (!ewoc && owoc == added_odd) ++cur;
return dp[added][ewoc][owoc][added_odd] = cur % mod;
}
int solve(int n1) {
n = n1;
for (int i = 0; i < n; ++i)
for (int j = 0; j < 6; ++j)
for (int k = 0; k < 6; ++k)
for (int l = 0; l < 6; ++l) dp[i][j][k][l] = -1;
// Loại trường hợp chọn phải số 0 vô nghĩa bằng cách đặt trước chữ số đầu tiên
long long tmp1 = digit_dp(1, 1, 0, 0) * 4;
long long tmp2 = digit_dp(1, 0, 1, 1) * 5;
return (tmp1 + tmp2) % mod;
}
int main(){
int n1;
while (cin >> n1) cout << solve(n1) << 'n';
}Bạn có thể tìm hiểu thêm về kĩ thuật quy hoạch động sử dụng đệ quy có nhớ (Top-Down) tại đây.
Vì số chữ số lẻ đã xuất hiện lẻ lần không được vượt quá số chữ số lẻ đã xuất hiện, nên ta tối ưu được số trạng thái xuống còn khoảng 6×6×6 / 2. Khi đó, độ phức tạp của thuật toán trên sẽ là O(n×(6×6×6 / 2))
.Tuy nhiên, với n≤1018
thì hiển nhiên thuật toán trên sẽ bị quá cả thời gian lẫn bộ nhớ.
Do đó, ta cần phải cải tiến thuật toán bằng lũy thừa ma trận với số trạng thái cho 1 lớp dp là 6×6×6 / 2=108
.Tối ưu hóa thuật toán bằng cách tách n thành các lũy thừa của 2 sau đó sử dụng các ma trận hệ số tương ứng đã tính toán trước để tính nhanh kết quả.
Cài đặt
Lưu ý: Trong cách cài đặt sau, các hàng và cột của ma trận được đánh số bắt đầu từ 0 để thuận tiện cho việc xử lí.
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 123;
using type = int;
struct Matrix {
vector <vector <type> > data;
int row() const { return data.size(); }
int col() const { return data[0].size(); }
auto & operator [] (int i) { return data[i]; }
const auto & operator[] (int i) const { return data[i]; }
Matrix() = default;
Matrix(int r, int c): data(r, vector <type> (c)) { }
Matrix(const vector <vector <type> > &d): data(d) { }
friend ostream & operator << (ostream &out, const Matrix &d) {
for (auto x : d.data) {
for (auto y : x) out << y << ' ';
out << 'n';
}
return out;
}
Matrix operator * (const Matrix &b) {
Matrix a = *this;
assert(a.col() == b.row());
Matrix c(a.row(), b.col());
for (int i = 0; i < a.row(); ++i)
for (int j = 0; j < b.col(); ++j)
for (int k = 0; k < a.col(); ++k){
c[i][j] += 1ll * a[i][k] % mod * (b[k][j] % mod) % mod;
c[i][j] %= mod;
}
return c;
}
};
int last;
int odd_id[6][6];
Matrix coef, base;
vector <Matrix> coef_pow;
int id(int ewoc, int owoc, int added_odd) {
assert(owoc <= added_odd);
return ewoc * last + odd_id[added_odd][owoc];
};
// Xây dựng ma trận hệ số
void build_coef() {
int ans_id = id(5, 5, 5) + 1;
coef = Matrix(ans_id + 1, ans_id + 1);
for (int added_odd = 0; added_odd <= 5; ++added_odd)
for (int ewoc = 0; ewoc <= 5; ++ewoc)
for (int owoc = 0; owoc <= added_odd; ++owoc) {
int cur_id = id(ewoc, owoc, added_odd);
if (ewoc)
coef[id(ewoc - 1, owoc, added_odd)][cur_id] += ewoc;
if (ewoc < 5)
coef[id(ewoc + 1, owoc, added_odd)][cur_id] += 5 - ewoc;
if (added_odd < 5)
coef[id(ewoc, owoc + 1, added_odd + 1)][cur_id] += 5 - added_odd;
if (owoc)
coef[id(ewoc, owoc - 1, added_odd)][cur_id] += owoc;
if (owoc < added_odd)
coef[id(ewoc, owoc + 1, added_odd)][cur_id] += added_odd - owoc;
if (!ewoc && owoc == added_odd) ++coef[ans_id][cur_id];
}
coef[ans_id][ans_id] = 1;
}
// Xây dựng ma trận cơ sở
void build_base() {
int ans_id = id(5, 5, 5) + 1;
base = Matrix(ans_id + 1, 1);
base[id(1, 0, 0)][0] = 4;
base[id(0, 1, 1)][0] = 5;
}
int main() {
last = 0;
for (int added_odd = 0; added_odd <= 5; ++added_odd)
for (int owoc = 0; owoc <= added_odd; ++owoc)
odd_id[added_odd][owoc] = ++last;
build_base();
build_coef();
// Tính lũy thừa ma trận hệ số tương ứng với lũy thừa của 2
coef_pow.push_back(coef);
for (int i = 1; i <= 60; ++i)
coef_pow.push_back(coef_pow[i - 1] * coef_pow[i - 1]);
long long n;
while (cin >> n) {
Matrix ans = base;
for (int i = 0; n > 0; n >>= 1, ++i)
if (n & 1) ans = coef_pow[i] * ans;
cout << ans[ans.row() - 1][0] << 'n';
}
}Đánh giá
Độ phức tạp
Ta mất độ phức tạp O(6×6×6 / 2)
cho việc xây dựng ma trận hệ số.
Vì ma trận kết quả có kích thước là ((số trạng thái) × 1) chứ không phải là ((số trạng thái) × (số trạng thái)), nên độ phức tạp nhân ma trận trong lúc tính kết quả là (số trạng thái)2 chứ không phải (số trạng thái)3. Nên độ phức tạp của thuật toán là O(log1018×1082)
.
Ngoài ra, kể cả khi ta không giảm số trạng thái xuống còn khoảng 6×6×6 / 2
thì thuật toán này vẫn đủ tốt.
Ví dụ 5
Bài toán
Ma trận
Ma trận là một mảng chữ nhật gồm các số, ký hiệu, hoặc biểu thức, sắp xếp theo hàng và cột mà mỗi ma trận tuân theo những quy tắc định trước.
Các ô trong ma trận được gọi là các phần tử của ma trận. Các phần tử được xác định bằng $2$ địa chỉ hàng $i$ và cột $j$ tương ứng (Kí hiệu là $a_{ij}$).
Ma trận thường được viết trong dấu ngoặc vuông:
$$
begin{bmatrix} a_{11} & a_{12} & … & a_{1n} newline a_{21} & a_{22} & … & a_{2n} newline vdots & vdots & ddots & vdots newline a_{m1} & a_{m2} & … & a_{mn} end{bmatrix}
$$
Độ lớn hay kích thước của ma trận được định nghĩa bằng số lượng hàng và cột. Một ma trận $m$ hàng và $n$ cột được gọi là ma trận $(m times n)$, trong khi $m$ và $n$ được gọi là chiều của nó.
-
Ví dụ: Ma trận $A$ là ma trận $(3 times 2)$
$A = begin{bmatrix} 1 & 2 newline 5 & 7 newline 6 & 3 end{bmatrix}$
Ma trận vuông
Ma trận vuông là ma trận có số hàng và số cột bằng nhau. Ma trận $(n times n)$ còn gọi là ma trận vuông cấp $n$. Các phần tử $a_{ii}$ tạo thành đường chéo chính của ma trận vuông.
-
Ví dụ: Ma trận vuông cấp $3$ (số hàng và số cột bằng $3$)
begin{bmatrix} 1 & 2 & 0 newline 3 & 0 & 1 newline 2 & 3 & 1 end{bmatrix}
Ma trận đơn vị (Identity Matrix)
Ma trận đơn vị $I_n$ cấp $n$ là một ma trận $(n times n)$ trong đó mọi phần tử trên đường chéo chính bằng $1$ và tất cả những phần tử khác đều bằng $0$. Ma trận đơn vị cấp $n$ cũng chính là ma trận vuông cấp $n$.
-
Ví dụ
$I_1 = begin{bmatrix} 1 end{bmatrix}$
$I_2 = begin{bmatrix} 1 & 0 newline 0 & 1 end{bmatrix}$
…
$I_n = begin{bmatrix} 1 & 0 & … & 0 newline 0 & 1 & … & 0 newline vdots & vdots & ddots & vdots newline 0 & 0 & … & 1 end{bmatrix}$
Vector hàng và vector cột
Vector hàng hay ma trận hàng là một ma trận $(1 times n)$, tức là ma trận chỉ gồm một một hàng đơn gồm $n$ phần tử.
$mathbf{a} = begin{bmatrix} a_1 & a_2 & … & a_n end{bmatrix}$
Vector cột hay ma trận cột là một ma trận $(m times 1)$, tức là ma trận chỉ gồm một cột đơn gồm $m$ phần tử.
$mathbf{b} = begin{bmatrix} b_1 newline b_2 newline vdots newline b_m end{bmatrix}$
Ta định nghĩa tích của vector hàng $mathbf{a}$ $(1 times n)$ với vector cột $mathbf{b}$ $(n times 1)$ tương đương với tích vô hướng của hai vector $mathbf{a}$ và $mathbf{b}$.
$mathbf{a} cdot mathbf{b} = begin{bmatrix} a_1 & a_2 & … & a_n end{bmatrix} begin{bmatrix} b_1 newline b_2 newline vdots newline b_n end{bmatrix} = displaystylesum_{i = 1}^{n} a_{i} b_{i} = a_1b_1+a_2b_2+…+a_nb_n$
Tham khảo: Vector hàng và cột
Ký hiệu[sửa | sửa mã nguồn]
Bài viết này sẽ sử dụng các quy ước công chứng sau: ma trận được thể hiện bằng chữ in hoa, ví dụ: A, vectơ in đậm chữ thường, ví dụ a và các mục của vectơ và ma trận là chữ nghiêng (vì chúng là số từ một trường), vd A và a. Ký hiệu chỉ mục thường là cách rõ ràng nhất để diễn đạt các định nghĩa và được sử dụng làm tiêu chuẩn trong tài liệu. i, j xâm nhập của ma trận A được chỉ định bởi (A)ij Aij aij trong khi một nhãn số (không phải mục ma trận) trên một tập hợp các ma trận được ghi chữ nhỏ ở dưới, ví dụ: A1, A2, v.v.
Định nghĩa[sửa | sửa mã nguồn]
Nếu A là ma trận m × n và B là ma trận n × p,
tích ma trận C = AB (ký hiệu không có dấu nhân hoặc dấu chấm) được xác định là ma trận m × p [3][4][5][6]
trong đó
với i = 1,…, m và j = 1,…, p.
Tham khảo[sửa | sửa mã nguồn]
- ^ Lerner, R. G.; Trigg, G. L. (1991). Encyclopaedia of Physics (ấn bản 2). VHC publishers. ISBN 978-3-527-26954-9.
- ^ Parker, C. B. (1994). McGraw Hill Encyclopaedia of Physics (ấn bản 2). ISBN 978-0-07-051400-3.
- ^ Lipschutz, S.; Lipson, M. (2009). Linear Algebra. Schaum’s Outlines (ấn bản 4). McGraw Hill (USA). tr. 30–31. ISBN 978-0-07-154352-1.
- ^ Riley, K. F.; Hobson, M. P.; Bence, S. J. (2010). Mathematical methods for physics and engineering. Cambridge University Press. ISBN 978-0-521-86153-3.
- ^ Adams, R. A. (1995). Calculus, A Complete Course (ấn bản 3). Addison Wesley. tr. 627. ISBN 0 201 82823 5.
- ^ Horn, Johnson (2013). Matrix Analysis (ấn bản 2). Cambridge University Press. tr. 6. ISBN 978 0 521 54823 6.
1. Ma trận là gì toán cao cấp?
Ma trận là một mảng hai chiều các số được sắp xếp thành các hàng và cột. Mỗi phần tử trong ma trận được định vị bằng một cặp chỉ số, thường là số nguyên không âm, một chỉ số dùng để xác định hàng và một chỉ số khác dùng để xác định cột. Ma trận thường được ký hiệu bằng chữ cái in hoa: A,B,C.
- Ma trận cỡ m x n là 1 bảng số hình chữ nhật gồm m hàng, n cột.
- Kí hiệu ma trận : A = (aij) m x n.
- Ví dụ dưới đây là một ma trận:
Ma trận mxn
Ma trận có nhiều hình dạng khác nhau tuỳ thuộc vào số hàng và cột. Thường thì ma trận với m hàng và n cột thường được gọi là ma trận m x n. Với ma trận có kích thước 1 x n được gọi là ma trận hàng, ma trận có kích thước m x 1 được gọi là ma trận cột. Ma trận cỡ n x n được gọi là ma trận vuông.
Với ma trận A là ma trận 3×4 có aij. Thì ma trận A được biểu thị như sau:
Tóm lại:
- Nếu ma trận cỡ m x n, thì nó có m hàng và n cột.
- Phần tử ma trận aij nghĩa là phần tử nằm ở hàng i cột j.
Ma trận cấp 2
Một ma trận cấp 2 là một ma trận có kích thước 2 hàng và 2 cột. Dưới đây là một ví dụ về ma trận cấp 2:
(begin{vmatrix}
1 & 2\
4 & 5
end{vmatrix})
Liên quan: trắc nghiệm đại số tuyến tính có đáp án
2. Các dạng ma trận
Ma trận 0
Ma trận 0 là các phần tử đều bằng 0.
Ma trận đường chéo
Ma trận đường chéo là ma trận vuông mà các phần tử ngoài đường chéo chính bằng 0.
Ma trận đơn vị
Ma trận đơn vị là ma trận có các phần tử đường chéo bằng 1.
Ma trận tam giác trên
Ma trận tam giác trên là ma trận vuông mà các phần tử nằm dưới đường chéo chính bằng 0.
Lưu ý: Nếu ma trận có đường chéo chính bằng 0, nó được gọi là ma trận tam giác trên.
Ví dụ:
(begin{vmatrix}
0 & 2& 3\
0 & 0& 0\
0 & 0& 0
end{vmatrix})
Ma trận tam giác dưới
Một ma trận tam giác dưới là một ma trận trong đó tất cả các phần tử nằm trên đường chéo chính và trên đường chéo chính đều bằng 0. Các phần tử trên đường chéo chính có thể là 0 hoặc khác 0. Dưới đây là một ví dụ về ma trận tam giác dưới:
(begin{vmatrix}
1 & 0& 0\
2 & 3& 0\
4 & 5& 6
end{vmatrix})
Trong ví dụ này, các phần tử nằm trên đường chéo chính và trên đường chéo chính đều bằng 0, và các phần tử còn lại có thể là bất kỳ giá trị nào. Ma trận tam giác dưới có dạng tam giác với các phần tử khác 0 chỉ nằm dưới đường chéo chính.
Ma trận chuyển vị của A
Ma trận bậc thang
- Nếu các hàng = 0 thì phải ở dưới cùng
- Nếu các hàng ≠ 0 thì phần tử đầu tiên của hàng dưới phải lệch sang phải phần tử ≠ 0 đầu tiên hàng trên
Xem thêm cách tính hạng của ma trận: Hạng của ma trận – bài tập & lời giải chi tiết
Định nghĩa Ma trận
Ma trận là một mảng chữ nhật gồm các số, ký hiệu, hoặc biểu thức, sắp xếp theo hàng và cột mà mỗi ma trận tuân theo những quy tắc định trước. Các ô trong ma trận được gọi là các phần tử của ma trận. Các phần tử được xác định bằng 2 địa chỉ hàng i và cột j tương ứng (Kí hiệu là aij
).
Ma trận thường được viết trong dấu ngoặc vuông:
Độ lớn hay kích thước của ma trận được định nghĩa bằng số lượng hàng và cột. Một ma trận m hàng và n cột được gọi là ma trận (m×n), trong khi m và n được gọi là chiều của nó.
Ví dụ: Ma trận A là ma trận (3×2)
Phép nhân ma trận
Trong đại số tuyến tính, ma trận đóng một vai trò quan trọng trong việc xử lý các khái niệm khác nhau. Một ma trận là một hình chữ nhật mảng hoặc bảng số, biểu tượng, hoặc biểu thức, sắp xếp theo hàng và cột trong toán học. Chúng ta có thể thực hiện các phép toán khác nhau trên ma trận như cộng, trừ, nhân, v.v. Trong bài này, bạn sẽ học cách nhân một ma trận với một ma trận khác, thuật toán, công thức, phép nhân ma trận 2 × 2 và 3 × 3 với các ví dụ chi tiết.
1.Định nghĩa phép nhân ma trận
Phép nhân ma trận, còn được gọi là tích ma trận và phép nhân hai ma trận, tạo ra một ma trận duy nhất. Nó là một loại hoạt động nhị phân .
Nếu A và B là hai ma trận thì tích của hai ma trận A và B được ký hiệu là:
X = AB
Do đó, tích của hai ma trận là tích chấm của hai ma trận.
2. Phép nhân ma trận bằng Vô hướng
Phép nhân một số nguyên với một ma trận chỉ đơn giản là một phép nhân vô hướng .
Chúng ta biết rằng ma trận là một mảng số. Nó bao gồm các hàng và cột. Nếu bạn nhân một ma trận với một giá trị vô hướng, thì nó được gọi là phép nhân vô hướng. Một trường hợp khác là có thể nhân một ma trận với một ma trận khác. Hãy cùng xem ví dụ dưới đây.
Chúng ta có thể định nghĩa phép nhân ma trận với một đại lượng vô hướng về mặt toán học là:
Nếu A = [a ij ] m × n là một ma trận và k là một vô hướng, thì kA là một ma trận khác thu được bằng cách nhân từng phần tử của A với k vô hướng.
Nói cách khác, kA = k [a ij ] m × n = [k (a ij )] m × n , nghĩa là, phần tử thứ (i, j) của kA là ka ij với tất cả các giá trị có thể có của i và j.
Ví dụ: Nhân ma trậnA = [3049– 15] bằng 4.
Giải pháp:
Được,
A = [3049– 15]
4 × A = 4 × [3049– 15]
Bây giờ, chúng ta phải nhân từng phần tử của ma trận A với 4.
= [1201636– 420]
Đây là ma trận bắt buộc sau khi nhân ma trận đã cho với giá trị hằng số hoặc vô hướng, tức là 4.
3. Điều kiện nhân ma trận
Để thực hiện phép nhân hai ma trận , chúng ta nên đảm bảo rằng số cột trong ma trận thứ nhất bằng số hàng trong ma trận thứ hai. Do đó, sản phẩm của ma trận thu được sẽ có một số hàng của ma trận thứ nhất và một số cột của ma trận thứ hai. Bậc của ma trận kết quả là bậc nhân ma trận .
Bây giờ, chúng ta hãy hiểu cách thực hiện phép nhân ma trận với các thứ tự khác nhau hoặc các loại ma trận khác nhau .
4. Làm thế nào để Nhân ma trận?
Chúng ta hãy học cách nhân ma trận.
Xét ma trận A là ma trận a × b và ma trận B là ma trận ab × c.
Khi đó, ma trận C = AB được định nghĩa là ma trận A × B.
Một phần tử trong ma trận C, C xy được xác định là C xy = A x1 B y1 +… .. + A xb B bởi = ∑bk = 1 A xk B ky cho x = 1 …… a và y = 1 …… .c
Đây là một trong những chuyên đề quan trọng nhất lớp 12. Bài giải ma trận lớp 12 giải chi tiết các dạng của ma trận.
Ký hiệu
Nếu A là ma trận am × n và B là ma trận ap × q, thì tích ma trận của A và B được biểu diễn bằng:
X = AB
Trong đó X là ma trận kết quả có kích thước m × q.
5. Công thức nhân ma trận
Hãy lấy một ví dụ để hiểu công thức này.
Giả sử A và B là hai ma trận, sao cho
A =⎡⎣⎢⎢⎢A11A21Am 1A12A22… … … … .Am 2⋯⋯⋯A1 nA2 nAm n⎤⎦⎥⎥⎥, B =⎡⎣⎢⎢⎢B11B21Bm 1B12B22… … … … .Bm 2⋯⋯⋯B1 nB2 nBm n⎤⎦⎥⎥⎥Khi đó Ma trận C = AB được ký hiệu là
C = ⎡⎣⎢⎢⎢C11C12… … .C1 cC21C22… … .C2 c… … … … …Cmột 1Cmột 2… … .Cmột c⎤⎦⎥⎥⎥
Một phần tử trong ma trận C trong đó C là phép nhân của Ma trận AX B.
C = C xy = A x1 B y1 +… .. + A xb B bởi = ∑bk = 1 A xk B ky cho x = 1 …… a và y = 1 …… .c
6. Thuật toán cho phép nhân ma trận
Trong những năm gần đây đã có rất nhiều công trình nghiên cứu trong lĩnh vực thuật toán nhân ma trận vì nó đã được tìm thấy ứng dụng của nó trong nhiều lĩnh vực. Có bốn loại thuật toán:
- Thuật toán lặp lại
- Thuật toán phân chia và chinh phục
- Thuật toán khối con
- Thuật toán song song và phân tán
Điều này chủ yếu được sử dụng trong các ngôn ngữ lập trình khác nhau như C, Java, v.v., để nhân trực tuyến. Phổ biến nhất là 2 × 2, 3 × 3 và 4 × 4, phép nhân ma trận.
Phép toán là nhị phân với các mục trong một tập hợp các phép toán cộng, trừ, nhân và chia được xác định. Các phép toán này giống như các phép toán tương ứng trên số thực và số hữu tỉ.
Mặc dù có nhiều ứng dụng của ma trận nhưng về cơ bản, phép nhân ma trận là một phép toán trong đại số tuyến tính. Ánh xạ tuyến tính, bao gồm phép cộng và phép nhân vô hướng, được biểu diễn bằng phép nhân ma trận.
Người ta cũng có thể tìm thấy một loạt các thuật toán trên các mắt lưới. Loại thuật toán này được thiết kế để giảm thiểu tính kém hiệu quả vốn có của các thuật toán mảng tiêu chuẩn, nơi có thể có độ trễ khi dữ liệu đến từ 2 ma trận khác nhau.
7. Quy tắc nhân ma trận
Từ công thức và quy trình đã xác định ở trên, chúng ta có thể viết các quy tắc và tính chất sau cho phép nhân ma trận.
Tích của hai ma trận A và B được xác định nếu số cột của A bằng số hàng của B.
Nếu AB được xác định, thì BA không cần được xác định
Nếu cả A và B đều là ma trận vuông cùng bậc thì cả AB và BA đều được xác định.
Nếu AB và BA đều xác định thì không cần AB = BA.
Nếu tích của hai ma trận là ma trận 0, thì không nhất thiết một trong hai ma trận là ma trận 0.
8. Phép nhân ma trận 2 × 2
Hãy xem xét một phép nhân ma trận 2 × 2 đơn giản A = [3479] và một ma trận khác B = [652số 8]
Bây giờ mỗi phần tử của ma trận tích AB có thể được tính như sau:
AB 11 = 3 × 6 + 7 × 5 = 53
AB 12 = 3 x 2 + 7 x 8 = 62
AB 21 = 4 × 6 + 9 × 5 = 69
AB 22 = 4 x 2 + 9 x 8 = 80
Do đó ma trận AB = [53696280]
9. Phép nhân ma trận 3 × 3
Để hiểu phép nhân hai ma trận 3 × 3, chúng ta hãy xét hai ma trận 3 × 3 A và B.
Ma trận A = ⎡⎣⎢1239số 817số 841410⎤⎦⎥, Ma trận B = ⎡⎣⎢5671915số 83916⎤⎦⎥
Mỗi phần tử của ma trận sản phẩm AB có thể được tính như sau:
AB 11 = 12 × 5 + 8 × 6 + 4 × 7 = 136
AB 12 = 12 x 19 + 8 x 15 + 4 x 8 = 380
AB 13 = 12 x 3 + 8 x 9 + 4 x 16 = 172
AB 21 = 3 × 5 + 17 × 6 + 14 × 7 = 215
AB 22 = 3 x 19 + 17 x 15 + 14 x 8 = 424
AB 23 = 3 x 3 + 17 x 9 + 14 x 16 = 386
AB 31 = 9 x 5 + 8 x 6 + 10 x 7 = 163
AB 32 = 9 x 19 + 8 x 15 + 10 x 8 = 371
AB 33 = 9 x 3 + 8 x 9 + 10 x 16 = 259
Do đó, ma trận AB = ⎡⎣⎢136215163380424371172386259⎤⎦⎥
Như vậy qua bài viết Phép nhân ma trận, Phép nhân 2 ma trận, Định nghĩa ma trận là gì? bạn đã biết cách giải bài toán về ma trận chưa. Hãy theo dõi bài viết để cùng tìm hiểu nhé.
Định nghĩa phép nhân ma trận
Phép nhân ma trận, còn được gọi là tích ma trận và phép nhân hai ma trận, tạo ra một ma trận duy nhất. Nó là một loại hoạt động nhị phân .
Nếu A và B là hai ma trận thì tích của hai ma trận A và B được ký hiệu là:
X = AB
Do đó, tích của hai ma trận là tích chấm của hai ma trận.
Phép nhân ma trận bằng Vô hướng
Phép nhân một số nguyên với một ma trận chỉ đơn giản là một phép nhân vô hướng .
Chúng ta biết rằng ma trận là một mảng số. Nó bao gồm các hàng và cột. Nếu bạn nhân một ma trận với một giá trị vô hướng, thì nó được gọi là phép nhân vô hướng. Một trường hợp khác là có thể nhân một ma trận với một ma trận khác. Hãy cùng xem ví dụ dưới đây.
Chúng ta có thể định nghĩa phép nhân ma trận với một đại lượng vô hướng về mặt toán học là:
Nếu A = [a ij ] m × n là một ma trận và k là một vô hướng, thì kA là một ma trận khác thu được bằng cách nhân từng phần tử của A với k vô hướng.
Nói cách khác, kA = k [a ij ] m × n = [k (a ij )] m × n , nghĩa là, phần tử thứ (i, j) của kA là ka ij với tất cả các giá trị có thể có của i và j.
Ví dụ: Nhân ma trậnA = [3049– 15] bằng 4.
Giải pháp:
Được,
A = [3049– 15]
4 × A = 4 × [3049– 15]
Bây giờ, chúng ta phải nhân từng phần tử của ma trận A với 4.
= [1201636– 420]
Đây là ma trận bắt buộc sau khi nhân ma trận đã cho với giá trị hằng số hoặc vô hướng, tức là 4.
Điều kiện nhân ma trận
Để thực hiện phép nhân hai ma trận , chúng ta nên đảm bảo rằng số cột trong ma trận thứ nhất bằng số hàng trong ma trận thứ hai. Do đó, sản phẩm của ma trận thu được sẽ có một số hàng của ma trận thứ nhất và một số cột của ma trận thứ hai. Bậc của ma trận kết quả là bậc nhân ma trận .
Bây giờ, chúng ta hãy hiểu cách thực hiện phép nhân ma trận với các thứ tự khác nhau hoặc các loại ma trận khác nhau .
