Mình xin chia sẻ lời giải bài này như sau:

Gọi \(G[n]\) là đáp án cần tìm. Khi đó ta có công thức truy hồi sau:

\(\left\{\begin{matrix}A[n] = 2*A[2]*A[n-1]-A[n-2] (\forall n\ge 3) \\ G[n]=G[n-1]+A[n]^2(\forall n\ge 2)\end{matrix}\right.\), trong đó: \(A[1]=1,A[2]=c,G[1]=1\) với \(c\) được nhập từ test.

Từ đây ta suy ra được:

\(\left\{\begin{matrix}A[n]^2 = 4c*A[n-1]^2-4c*A[n-1]*A[n-2]+A[n-2]^2 \\ A[n]*A[n-1] = 2c*A[n-1]^2-A[n-1]*A[n-2]\\G[n]=G[n-1]+A[n]^2(\forall n\ge 2)\end{matrix}\right.\), trong đó: \(A[1]=1,A[2]=c,G[1]=1\) với \(c\) được nhập từ test.

Nên từ đây, ta suy ra được công thức truy hồi với ma trận như sau:

\(\begin{pmatrix}G[n-2]&F[n-1]^2&F[n-1] * F[n-2]&F[n-2]^2\end{pmatrix}.\begin{pmatrix}1&0&0&0\\1&4c^2&2c&1\\0&-4c&-1&0\\0&1&0&0\end{pmatrix}=\begin{pmatrix}G[n-1]&F[n]^2&F[n]*F[n-1]&F[n-1]^2\end{pmatrix}\)

Tiếp theo, đặt \(p_n=\begin{pmatrix}G[n-1]&F[n]^2&F[n] * F[n-1]&F[n-1]^2\end{pmatrix}\) và \(M=\begin{pmatrix}1&0&0&0\\1&4c^2&2c&1\\0&-4c&-1&0\\0&1&0&0\end{pmatrix}\). Ta được: \(p_{n+1}=p_{n}.M=...=p_2.M^{n-1}\)

Với \(p_2=\begin{pmatrix}1&c^2&c&1\end{pmatrix}\)

Sau khi dùng luỹ thừa nhị phân ta tính được \(p_{n+1}\) ta được \(G[n]\) chính là giá trị cần tìm.

Các bạn có thể tham khảo code tại đây

Ps: Mình nghĩ mấu chốt của những bài như vậy, là ta phải thiết kế được \(p_n\) sao cho có thể tạo được dãy truy hồi với ma trận, và cuối cùng nếu có gì thắc mắc, các bạn cứ comment nhé .

Chú ý: Các bạn cần xử lý mod với số âm để không bị sai kết quả nhé!