NKPATH - Đường đi trên lưới
Giới hạn- Thời gian: 5.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho một lưới ô vuông gồm m dòng và n cột. Các dò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 ở vị trí dòng i và cột j của lưới được gọi là ô (i, j) và khi đó, i được gọi là tọa độ dòng còn j được gọi là tọa độ cột của ô này. Trên ô (i, j) của lưới ghi số nguyên dương a ij , i = 1, 2, …, m; j = 1, 2, …, n. Trên lưới đã cho, từ ô (i, j) ta có thể di chuyển đến ô (p, q) nếu các điều kiện sau đây được thỏa mãn:
- j < n; i ≤ p; j ≤ q và i + j < p + q;
- a ij và a pq có ước số chung lớn hơn 1.
Ta gọi một cách di chuyển từ mép trái sang mép phải của lưới là cách di chuyển bắt đầu từ một ô có tọa độ cột bằng 1 qua các ô của lưới theo qui tắc di chuyển đã nêu và kết thúc ở một ô có tọa độ cột bằng n.
Yêu cầu: Tính số cách di chuyển từ mép trái lưới sang mép phải lưới.
Dữ liệu vào
- Dòng đầu tiên ghi 2 số nguyên dương m, n.
- Dòng thứ i trong số m dòng tiếp theo ghi n số nguyên dương a i1 , a i2 , …, a in là các số trên dòng thứ i của lưới, i = 1, 2, …, m.
Hai số liên tiếp trên cùng một dòng được ghi cách bởi ít nhất một dấu cách.
Kết qủa
Ghi ra 1 số nguyên là phần dư của số lượng cách di chuyển tìm được cho 10 9 .
Hạn chế
Trong tất cả các test: 1 < m, n ≤ 100; a ij ≤ 30000, i=1,2,…,m;j=1,2,…,n. Có 50% số lượng test với m, n ≤ 50.
Ví dụ
Dữ liệu mẫu 2 2 2 4 6 8 Kết qủa 4 Dữ liệu mẫu 2 2 2 5 6 7 Kết qủa 0
- Người up: paulmcvn
- Nguồn bài: Ðề thi quốc gia 2006