cpp-206Bước 1Trung bình
Phép Nhân Hai Ma Trận Vuông
Phép nhân ma trận là nền tảng cốt lõi của đại số tuyến tính, đồ họa 3D và toàn bộ các kiến trúc mạng nơ-ron sâu (Deep Learning / Transformer). Việc cài đặt chính xác thuật toán nhâ…
CHUYÊN ĐỀ C++ THỰC CHIẾN
Bài tập Đại số tuyến tính & Nhân ma trận nhanh trong C++
Kết hợp toán học ma trận với thuật toán lũy thừa nhị phân để giải quyết các hệ thức truy hồi tuyến tính với N lên tới 10^18 trong nháy mắt.
8
bài tập có chấm code
Bài tập theo chuyên đề, có đề bài, ví dụ và starter code riêng.
0
cơ bản
Củng cố nền tảng và làm quen với kỹ thuật cốt lõi.
1
trung bình
Kết hợp nhiều bước suy luận để vận dụng kiến thức.
7
nâng cao
Thử thách tối ưu, cấu trúc dữ liệu và thuật toán chuyên sâu.
Lộ trình thực hành đề xuất
Bước 1
Cấu trúc Ma trận
Xây dựng struct Matrix kích thước K x K và phép nhân hai ma trận có chia dư modulo.
Bước 2
Lũy thừa ma trận nhị phân
Tính Matrix^N trong O(K^3 log N) bằng thuật toán chia đôi số mũ.
Bước 3
Chuyển đổi hệ thức truy hồi
Thiết lập ma trận chuyển trạng thái cho dãy Fibonacci, Tribonacci và bài toán đếm đường đi.
Lỗi thường gặp & Cách phòng tránh
•
Tràn số khi nhân hai phần tử ma trận (cần ép kiểu long long trước khi modulo).
•
Kích thước ma trận chuyển trạng thái bị lệch hàng hoặc cột.
Danh sách bài tập thực hành (8 bài)
Trong mỗi mức độ, bài tập được xếp từ dễ nhất đến khó nhất — hãy đi theo số bước.
Trung bình 1 bài
Nâng cao 7 bài
Thử thách
Thuật toán chuyên sâu: quy hoạch động, đồ thị, cây.
cpp-080Bước 1Nâng cao
Khử Gauss và Cơ sở tuyến tính không gian XOR (Linear Basis)
Cho một tập hợp gồm N số nguyên dương A1, A2, …, AN. Bạn hãy chọn ra một tập hợp con bất kỳ (có thể rỗng, tổng XOR của tập rỗng quy ước bằng 0) sao cho giá trị XOR của các p…
cpp-196Bước 2Nâng cao
Thuật toán Berlekamp-Massey: Tìm công thức truy hồi tuyến tính và số hạng thứ N
Cho 2K số hạng đầu tiên của một dãy số A: A0, A1, A2, …, A2K-1 thỏa mãn một hệ thức truy hồi tuyến tính ẩn có bậc không vượt quá K:
cpp-070Bước 3Nâng cao
Biến đổi Fourier nhanh: Thuật toán FFT nhân đa thức O(N log N)
Cho hai đa thức A(x) = ∑i=0N ai xi và B(x) = ∑j=0M bj xj với các hệ số ai, bj là các số nguyên không âm.
cpp-034Bước 4Nâng cao
Nhân ma trận nhị phân tính số Fibonacci thứ N lớn
Dãy số Fibonacci được định nghĩa:
Chuyên sâu
Cấu trúc dữ liệu nâng cao và nhiều bước chứng minh.
cpp-071Bước 5Nâng cao
Biến đổi số học NTT modulo 998244353
Cho hai đa thức A(x) = ∑i=0N ai xi và B(x) = ∑j=0M bj xj. Hãy tính các hệ số của đa thức tích C(x) = A(x) · B(x) mod 998244353.
cpp-115Bước 6Nâng cao
Đếm Cây Khung Bằng Định Lý Ma Trận Kirchhoff (Matrix Tree Theorem)
Cho đơn đồ thị vô hướng G = (V, E) gồm N đỉnh và M cạnh. Đồ thị có thể có nhiều cạnh nối giữa cùng một cặp đỉnh (đa đồ thị), các khuyên tự nối (self-loops) được bỏ qua vì không thể…
cpp-195Bước 7Nâng cao
Biến đổi Fourier nhanh (FFT): Nhân hai đa thức bậc cao trong O(N log N)
Cho hai đa thức A(x) có bậc N và B(x) có bậc M: