Số đường đi
View as PDF
Submit solution
Points:
400 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Author:
Problem types
Cho lưới ô vuông kích thước ~n× m~, ô (~1, 1~) ở góc dưới trái, ô (~n,m~) – trên phải. Có ~k~ ô chứa chướng ngại vật, ô thứ ~i~ ở tọa độ (~x_i, y_i~), ~1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m, i = 1 ÷ k~, Không có chướng ngại vật ở ô (~1, 1~) và (~n, m~).
Rô bốt xuất phát từ ô (~1, 1~), ở mỗi bước được chuyển sang ô kề cạnh bên phải hoặc bên trên nếu ô tới không chứa chướng ngại vật.
Hãy xác định số lượng đường rô bốt có thể đi từ ô (~1, 1~) đến ô (~n, m~) và đưa ra số lượng theo mô đun ~p~, trong đó ~p~ – số nguyên tố.
Dữ liệu
- Dòng đầu tiên chứa 4 số nguyên ~n, m, k, p~ (~1 ≤ n, m ≤ 10^5, 0 ≤ k ≤ 100,2 \times max{m,n} < p < 2 × 10^9~),
- Nếu ~k > 0~, dòng thứ ~i~ trong ~k~ dòng tiếp theo chứa 2 số nguyên ~x_i, y_i~ (~1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m~).
Kết quả
- Đưa ra một số nguyên không âm – số lượng đường tìm được theo mô đun ~p~.
Sample input
5 6 3 101
2 2
3 5
4 2Sample output
25Nguồn: Thầy Tùng
View comments (1)
Comments
Bài này rất hay, nhưng em chưa biết làm. Các anh/ chị/ thầy/ cô đã AC có thể viết Solution cho em tham khảo được không ạ? Em cảm ơn.