Bài toán nhảy về đích

[Ktoonovip (Dũng)]

Xét bảng hình chữ nhật kích thước m x n ô. Các hàng được đánh số từ 1 đến m từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái qua phải. Ô nằm trên hàng i và cột j được ghi một số nguyên không âm ký hiệu Cij. Ở góc trên trái bảng có một quân cờ. Ta phải chuyển quân cờ về ô dưới phải của bảng theo quy tắc sau:

• Tại mỗi bước nhảy, chỉ được di chuyển sang phải trên cùng một hàng hoặc di chuyển xuống dưới theo cùng một cột
• Kích thước bước nhảy không được vượt quá số ghi trên ô có quân cờ hiện tại
• Chỉ được di chuyển trong phạm vi bảng đang xét

Kích thước của bước nhảy từ ô (i, j) tới ô (u, v) được tính bằng giá trị u + v - i - j .

Yêu cầu: Cho dãy a1, a2,…,am, b1, b2,…, bn và số nguyên dương k. Bảng kích thước m x n được xác định với:
Cij = 1 + [(ai + bj) mod k]
Hãy tính số lượng cách di chuyển quân cờ từ ô trên trái (1 , 1) xuống ô dưới phải (m, n).

Dữ liệu vào :

• Dòng đầu chứa 3 số nguyên dương m, n, k ( m, n, k <= 4. 10^3)
• Dòng thứ hai chứa m số nguyên a1, a2, …, am (0 <= ai <= 1e9)
• Dòng thứ ba chứa n số nguyên b1, b2, …, bn (0 <= bi <=1e9)

Kết quả: Một số nguyên duy nhất là số cách di chuyển tìm được lấy theo module 1e9 + 7 .

Ví dụ:
INPUT:
3 2 2
3 4 11
2 5
OUTPUT:
4

Ràng buộc:

• 70 % số test có m, n <= 1e3
• 30% số test còn lại tương ứng 30% số điểm không có ràng buộc gì thêm

Cho em hỏi thuật toán bài này được không ạ . Em cảm ơn nhiều ạ!

[Phong_Ky_Vo (Tao Không Ngu.)]

Hi Vô danh 2k3.
Hãy giới hạn bài toán lại một chút.

1. Thay vì bàn cờ thì bạn có một dẫy các ô [X][ ][ ][ ][ ][ ][ ][ ][Y].
2. Xuất phát từ vị trí X đi đến Y.
3. Chỉ được đi từ trái sang phải.
4. Mỗi bước đi 1 ô.
   -> Có bao nhiêu cách đi ?
   Mở rộng bài toán, không chỉ là đi trái sang phải mà có thể lên xuống, và độ dài bước nhẩu từ 1 đến max. Sau khi có cách đi suy nghĩ một chút về trạng thái bài toán qua các bước.

[tcm (Người bí ẩn)]

Nếu mình nhớ không nhầm thì bài này có đến khoảng 4, 5 subtasks thì phải, đề trại hè Hùng Vương vừa rồi. Cách làm chi tiết như sau:

• 2 subtasks đầu ta đếm số đường đi trên lưới, từ ô (1,1) đến ô (m,n).
• Các subtasks còn lại:
  Gọi F[i][j] là số cách di chuyển tới ô (m, n) từ ô (i, j). Vì chỉ được đi sang phải hoặc xuống dưới, ta dễ dàng suy ra CTQHĐ:
  F[i][j] = F[x][j] + F[i][y] với lần lượt i + 1 <= x <= min(i + C[i][j] + 1, m + 1) và j + 1 <= y <= min(j + C[i][j] + 1, n + 1).
  Cơ sở QHĐ: F[m][n] = 1.
  Kết quả: F[1][1].
  Độ phức tạp của cách trên là: O(m*n*k).
  Để giảm xuống O(m*n), ta dùng một mảng cộng dồn. Gọi right[i][j] là tổng hậu tố F[i][j] + F[i][j + 1] + F[i][j + 2] + … + F[i][n] và down[i][j] là tổng hậu tố F[i][j] + F[i + 1][j] + … + F[m][j].
  Ta tính hai mảng cộng dồn song song với quá trình tính mảng F và lưu kết quả.

Source code của mình (nếu bạn cần tham khảo): https://ideone.com/ChQ0oA