Editorial for Matrix Exponentiation - Recurrence With Square
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Note: Các bạn có thể
- Đọc Blog về Nhân ma trận của VNOI
- Làm bài Fibonacci trước để hiểu thêm về nhân ma trận trước khi thử sức với bài này
Lưu ý rằng tất cả các ma trận đuợc nhắc đến trong editorial này đều ~1~-indexed (các chỉ số từ ~1~ đến ~n~)
Ta xét bài toán con sau: Tính tổng ~\sum_{i = 1}^n i^2~ = ~1^2 + 2^2 + ... + n^2~ ~(n \leq 10^{18})~
Dù bài toán này có thể giải trong ~O(1)~ bằng công thức, mình sẽ trình bày lời giải bằng nhân ma trận:
Ta lưu một ma trận ~1 \cdot 4~ chứa lần lượt ~\sum_{j = 1}^i j^2~, ~1~, ~(i + 1)~, ~(i + 1)^2~
Ta cần chuyển từ ma trận với ~i~ sang ma trận với ~(i + 1)~
Hay nói cách khác, ta cần chuyển từ ~\begin{bmatrix}\sum_{j = 1}^i j^2\\ 1\\ (i + 1)\\ (i + 1)^2)\end{bmatrix}~ sang ~\begin{bmatrix}\sum_{j = 1}^{i + 1} j^2\\ 1\\ (i + 2)\\ (i + 2)^2\end{bmatrix}~
Ma trận ~4\cdot4~ để biến đổi như sau: ~\begin{bmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 2 & 1 \\ \end{bmatrix}~
Giải thích:
~\begin{bmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 2 & 1 \\ \end{bmatrix} \times \begin{bmatrix} \sum_{j = 1}^i j^2 \\ 1 \\ i + 1 \\ (i + 1)^2 \end{bmatrix} = \begin{bmatrix} \left(\sum_{j = 1}^i j ^ 2 \right) + (i + 1)^2 \\ 1 \\ (i + 1) + 1 \\ (i + 1) ^ 2 + 2(i + 1) + 1 \end{bmatrix} = \begin{bmatrix} \sum_{j = 1}^{i + 1} j^2 \\ 1 \\ i + 2 \\ (i + 2)^2 \end{bmatrix}~
Bây giờ, chúng ta có thể quay lại với bài chính:
Ta lưu một ma trận ~1 \cdot (n + 3)~ chứa lần luợt ~a_{i}, a_{i - 1}, ..., a_{i - n + 1}, 1, (i + 1), (i + 1)^2~
Ma trận ~trans~ kích thuớc ~(n + 3) \cdot (n + 3)~ để chuyển từ ~i~ sang ~(i + 1)~ như sau:
- ~Trans[i + 1][i] = 1, \forall 1 \leq i \leq (n - 1)~
- ~Trans[1][i] = c[i], \forall 1 \leq i \leq n~
- ~Trans[1][n + 1] = p, Trans[1][n + 2] = q, Trans[1][n + 3] = r~
- ~Trans[n + 1][n + 1] = 1~
- ~Trans[n + 2][n + 1] = 1, Trans[n + 2][n + 2] = 1~
- ~Trans[n + 3][n + 1] = 1, Trans[n + 3][n + 2] = 2, Trans[n + 3][n + 3] = 1~
Giải thích:
- Dòng ~1~: Chuyển ~a_{i}, a_{i - 1}, ..., a_{i - n + 2}~ sang một vị trí
- Dòng ~2~ và ~3~: Tính ~a_{i + 1}~ theo công thức
- Dòng ~4~: ~1 = 1~
- Dòng ~5~: ~(n + 2) = (n + 1) = 1~
- Dòng ~6~: ~(n + 2)^2 = (n + 1)^2 + 2(n + 1) + 1~
Độ phức tạp: ~O(n^3 \cdot log_2(k))~
Comments