Số cách đi quân mã (OLP 30/4 2023)

Điểm: 1400 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: SOCACH.inp

Output: SOCACH.out

Tác giả:

Dạng bài

Xét một bàn cờ vua có kích thước $m \times n$ có $m$ hàng $n$ cột.

Các hàng được đánh số từ $1$ đến $m$ và các cột được đánh số từ $1$ đến $n$ .

Một quân mã xuất phát từ một ô trên bàn cờ có thể đi đến một trong bốn ô như hình vẽ.

Ngoài ra, trên bàn cờ có $k$ ô mà quân mã không được phép đi vào. Những ô này được gọi là những ô bị cấm.

Yêu cầu: Tìm số cách di chuyển của quân mã từ ô $(x, y)$ đến ô $(m, n)$ .

Input, Output và Subtasks

Input: (SOCACH.inp)

Dòng đầu ghi $4$ số nguyên dương $m, n, k, Q$ $(1 < m, n \le 1000; 0 \le k \le 10; Q \le 10^5)$ .
Trên $k$ dòng tiếp theo, mỗi dòng ghi hai số nguyên $k_{x_i}, k_{y_i}$ cho biết ô $(k_{x_i}, k_{y_i})$ bị cấm.
Trên $Q$ dòng tiếp theo, mỗi dòng ghi hai số nguyên dương $x_i, y_i$ .

Các số ghi trên một dòng cách nhau ít nhất một khoảng trắng.

Output: (SOCACH.out)

Gồm $Q$ số nguyên $W_i$ , mỗi số trên một dòng cho biết số cách di chuyển quân mã từ ô $(x_i, y_i)$ cho trước đến ô $(m, n)$ .
Trong đó, số nguyên $W_i$ là phần dư của phép chia số cách di chuyển quân mã từ ô $(x_i, y_i)$ cho trước đến ô $(m, n)$ cho $10^9$ .

Subtasks

Sample

Input (SOCACH.inp)

Output (SOCACH.out)

1
1
0

Note

Bình luận