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))~