¶ Nhân ma trận (Matrix multiplication)
Nguồn: Biên soạn lại từ bài viết của Nguyễn RR Thành Trung, Nguyễn Mạnh Quân.
Tác giả:
- Nguyễn Châu Khanh - VNU University of Engineering and Technology (VNU-UET)
- Bùi Minh Hoạt - VNU University of Engineering and Technology (VNU-UET)
Reviewer:
- Trần Quang Lộc - ITMO University
- Hồ Ngọc Vĩnh Phát - VNUHCM-University of Science
- Trần Xuân Bách - HUS High School for Gifted Students
- Nguyễn Phú Bình - Hung Vuong High School for the Gifted, Binh Duong Province
¶ Mở đầu
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
Tham khảo: Ma trận_wikipedia
¶ 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 địa chỉ hàng và cột tương ứng (Kí hiệu là ).
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 hàng và cột được gọi là ma trận , trong khi và được gọi là chiều của nó.
-
Ví dụ: Ma trận là ma trận
¶ 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 còn gọi là ma trận vuông cấp . Các phần tử 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 (số hàng và số cột bằng )
¶ Ma trận đơn vị (Identity Matrix)
Ma trận đơn vị cấp là một ma trận trong đó mọi phần tử trên đường chéo chính bằng và tất cả những phần tử khác đều bằng . Ma trận đơn vị cấp cũng chính là ma trận vuông cấp .
-
Ví dụ
...
¶ Vector hàng và vector cột
Vector hàng hay ma trận hàng là một ma trận , tức là ma trận chỉ gồm một một hàng đơn gồm phần tử.
Vector cột hay ma trận cột là một ma trận , tức là ma trận chỉ gồm một cột đơn gồm phần tử.
Ta định nghĩa tích của vector hàng với vector cột tương đương với tích vô hướng của hai vector và .
Tham khảo: Vector hàng và cộ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 có kích thước và ma trận có kích thước , thì ma trận tích có kích thước , phần tử đứng ở hàng thứ , cột thứ xác định bởi công thức:
(Với )
Hay viết , tức là phần tử ở hàng thứ , cột thứ của là tích của vector hàng thứ của ma trận với vector cột thứ của ma trận .
- Minh họa tích ma trận của hai ma trận và :
-
Ví dụ: Cho ma trận
và
Phần tử của ma trận tích là tích của vector hàng thứ nhất của và vector cột thứ hai của , ta có:
Tính tương tự với tất cả phần tử còn lại của ma trận tích . Ta được ma trận tích có dạng:
Mô tả quá trình nhân ma trận:
¶ Tính chất của phép nhân ma trận
- Tính chất kết hợp: .
- Tính chất phân phối: , cũng như .
- Phép nhân ma trận không có tính chất giao hoán: Tích có thể xác định trong khi không nhất thiết phải xác định, tức là nếu và lần lượt có số chiều và , và . 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à .
-
Ví dụ:
, trong khi .
-
- 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à: (với ma trận kích thước bất kỳ).
Cũng chính vì tính chất này mà có tên gọi là ma trận đơn vị.
Bạn có thể tìm hiểu thêm về phép cộng trừ ma trận tại đây.
¶ Lũy thừa ma trận
Cho ma trận vuông cấp . Khi đó ta có phép tính ma trận lũy thừa (kí hiệu: ), với là một số nguyên không âm.
Trường hợp đặc biệt: Với , ma trận được xác định là ma trận đơn vị có cùng kích thước, tức là .
-
Ví dụ: Cho ma trận vuông cấp
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 với là số nguyên). Bạn có thể tìm hiểu về cách tính hàm mũ tại đây.
¶ 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ừ để 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
}
Bạn có thể tham khảo thêm cách cài đặt khác tại đây.
¶ Đá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
Nhân ma trận: Với ma trận kích thước và ma trận kích thước . Độ phức tạp của thuật toán để tính là .
- Ghi chú: Đối với phép nhân các ma trận vuông kích thước , có thuật toán nhân ma trận Strassen với độ phức tạp theo tư tưởng chia nhỏ ma trận (tương tự cách nhân nhanh số lớn). Tuy nhiên cài đặt rất phức tạp và trên thực tế với giá trị thường gặp, cách này không chạy nhanh hơn nhân ma trận thông thường .
Lũy thừa ma trận: Với ma trận vuông cấp , thuật toán tính có độ 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 . Hãy đếm số cách lát các viên gạch nhỏ kích thước và 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 là số cách lát các viên gạch nhỏ vào hình chữ nhật kích thước . Ta có:
- Nếu sử dụng viên gạch kích thước thì .
- Nếu sử dụng viên gạch kích thước thì .
.
Do đó, bài toán quy về tìm số thứ với dãy được định nghĩa như sau:
(với )
Hiển nhiên cách làm thông thường là tính lần lượt các . Tuy nhiên, cách làm này hoàn toàn không hiệu quả với lên đến , và ta cần một cách tiếp cận khác.
Ta xét các lớp số:
- Lớp :
- Lớp :
- Lớp :
- Lớp :
- Lớp :
Ta hình dung mỗi lớp là một ma trận . Tiếp đó, ta sẽ biến đổi từ lớp đến lớp . Sau mỗi lần biến đổi như vậy, ta tính thêm được một giá trị . Để 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:
Chắc hẳn đọc đến đây bạn đọc sẽ thắc mắc, làm thế nào để tìm được ma trận ? Để tìm được ma trận này, ta làm như sau:
Suy ra:
- , do đó hàng đầu tiên của ma trận là .
- , do đó hàng thứ hai của ma trận là .
Ta có:
vì
(vì và )
Ma trận còn được gọi là ma trận hệ số và ma trận được gọi là ma trận cơ sở.
Vậy bài toán trên được đưa về dạng nhân ma trận. được tính dựa vào phép lũy thừa của ma trậ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ừ để 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à . Với 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
Cho dãy số nguyên độ dài () là và với . Dãy số được xác định như sau:
- (với )
- (với )
Yêu cầu: Tính với . Đáp án in ra theo modulo .
¶ Phân tích
Cũng như trong ví dụ 1, ta xét các lớp số:
- Lớp :
- Lớp :
- Lớp :
Mỗi lớp là một ma trận . Ta cũng sẽ áp dụng phép nhân ma trận để biến đổi từ lớp sang lớp như sau:
Để xây dựng ma trận vuông như trên, ta thực hiện tương tự như trong ví dụ trước: Phân tích đến dưới dạng :
- nên hàng đầu tiên của ma trận là .
- nên hàng thứ hai của ma trận là .
- nên hàng thứ của ma trận là .
- nên hàng thứ của ma trận là .
Từ đó, ta thu được cách làm như trong ví dụ 1. Vì ta cần tính nên chỉ cần xác định đến lớp .
(vì với )
¶ 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ừ để 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à . Với 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 bầy , đánh số từ đến . 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ừ đến , tại giây thứ thì quy luật được áp dụng sẽ là .
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 đơn vị thời gian , mỗi bầy có bao nhiêu vi khuẩn.
Các loại quy luật có thể có:
A i 0: Tất cả các vi khuẩn thuộc bầy chết.B i k: Số vi khuẩn trong bầy tăng lên gấp lần .C i j: số vi khuẩn trong bầy tăng lên một số lượng bằng với số vi khuẩn trong bầy .D i j: Các vi khuẩn thuộc bầy di chuyển toàn bộ sang bầy .E i j: Các vi khuẩn thuộc bầy và bầy đổi vị trí cho nhau.F 0 0: Vị trí các vi khuẩn di chuyển trên vòng tròn. Nghĩa là các vi khuẩn ở bầy di chuyển sang bầy . Các di chuyển xảy ra đồng thời.
¶ 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 với là độ phức tạp cho xử lý số lớn. Cách này không thể chạy được với 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 bầy tại một thời điểm xác định là một ma trận , và mỗi phép biến đổi là một ma trậ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 , 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ừ xuống . 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 là các ma trận tương ứng với các phép biến đổi được cho.
Đặt .
Đặt (dãy số lượng vi khuẩn tại thời điểm đầu tiên).
Như vậy, là ma trận thể hiện số lượng vi khuẩn tại thời điểm .
Như vậy, thuật toán đến đây đã rõ. Ta phân tích , nhờ đó, ta có thể giải quyết bài toán trong cho bước tính ma trận và cho bước tính . 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 đề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 cũng xuấn hiện chẵn lần nếu nó xuất hiện. Ví dụ số là một số đẹp. Gọi là số lượng số đẹp có không quá chữ số. Yêu cầu với một số tính .
¶ Phân tích
Cách làm đơn giản nhất là ta sử dụng quy hoạch động với trạng thái:
added: số lượng chữ số đã thêm vào.ewoc(even_with_odd_cnt) : số chữ số chẵn đã xuất hiện lẻ lần.owoc(odd_with_odd_cnt) : số chữ số lẻ đã xuất hiện lẻ lần.added_odd: số chữ số lẻ đã xuất hiện.
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 . Khi đó, độ phức tạp của thuật toán trên sẽ là .
Tuy nhiên, với 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 lớp là .
Tối ưu hóa thuật toán bằng cách tách thành các lũy thừa của 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ừ để 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 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) 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) chứ không phải (số trạng thái). Nên độ phức tạp của thuật toán là .
Ngoài ra, kể cả khi ta không giảm số trạng thái xuống còn khoảng thì thuật toán này vẫn đủ tốt.
¶ Ví dụ 5
¶ Bài toán
Codeforces - 446C DZY Loves Fibonacci Numbers
Dãy được định nghĩa như sau:
Cho một dãy gồm số nguyên: