Bình luận

• 
  

  0

  

  vudinhlong  đã bình luận lúc 28, Tháng 6, 2026, 10:44 ← sửa 2 →

  Lời giải (không chính thức)

  Subtask ~1~ và ~2~: Quy hoạch động

  Gọi ~dp[n][s]~ là số cách xây dựng thoả mãn yêu cầu đề bài (trừ tiêu chí ~1~, tức là không chọn ô nào) khi xét đến vị trí ~n~ và có tổng số lượng ô chọn chia dư cho ~k~ bằng ~s~.

  Như vậy, đáp số bài toán sẽ là ~dp[m][0] - 1~ (do tính thêm cả trường hợp không chọn ô nào).

  Nhận xét tiếp theo là có tối đa ~7~ cấu hình có thể xây cho vị trí thứ ~i~.

  Có ~1~ cấu hình có tổng là ~0~: ~000~.

  Có ~3~ cấu hình có tổng là ~1~: ~001~, ~010~, ~100~.

  Có ~3~ cấu hình có tổng là ~2~: ~011~, ~110~, ~101~.

  ~\to~ Công thức truy hồi: ~dp[i][s] = dp[i - 1][s] + 3 \times dp[i - 1][s - 1] + 3 \times dp[i - 1][s - 2]~.

  Lưu ý: do số lượng ô chọn ~s~ đã được chia dư cho ~k~, nên ví dụ ~dp[i][0] = dp[i - 1][0] + 3 \times dp[i - 1][k - 1] + 3 \times dp[i - 1][k - 2]~.

  Độ phức tạp: ~O(m \times k)~.

  Subtask ~3~: Nhân ma trận

  Với ~m~ có thể lên tới ~5 \times 10^8~, ta sẽ phải sử dụng nhân ma trận để tối ưu tốc độ.

  Ta sẽ có ~2~ ma trận tạm gọi là ~a~ và ~t~, có kích thước ~k \times k~, chỉ số chạy từ ~0 \to k - 1~.

  Trong đó ma trận ~a~ sẽ là ma trận cơ sở ở vị trí ~0~ (tức là chỉ có hàng ~1~ chứa các giá trị ~dp[0][0 \to k - 1]~) và chỉ có ~dp[0][0] = 1~ do không chọn ô nào.

  Ma trận ~t~ ta sẽ xây dựng dựa trên công thức truy hồi, cụ thể các bạn có thể xem ví dụ với ~k = 5~ dưới đây:

  $$ \begin{bmatrix} 1 & 3 & 3 & 0 & 0 \\ 0 & 1 & 3 & 3 & 0 \\ 0 & 0 & 1 & 3 & 3 \\ 3 & 0 & 0 & 1 & 3 \\ 3 & 3 & 0 & 0 & 1 \\ \end{bmatrix} $$

  ~\to~ Ta sẽ phải tính ~a \times t^m~ do ma trận cơ sở đang ở vị trí ~0~ và ~dp[m][0]~ ở trên chính là phần tử ~a[0][0]~ sau khi nhân.

  Độ phức tạp: ~O(k^3 \times log(m))~.