Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKPATH - Đường đi trên lưới

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nkpath


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 aij, 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;
  • aij và apq 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 ai1, ai2, …, ain 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 109.

Hạn chế

Trong tất cả các test: 1 < m, n ≤ 100; aij ≤ 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

Được gửi lên bởi:Jimmy
Ngày:2007-12-27
Thời gian chạy:5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Đề thi quốc gia 2006

hide comments
2014-12-04 14:44:22 KPDFSVD
test đề phải ra 5 chứ
2 - 4
2 - 8
6 - 8
2 - 6 - 8
2 - 4 - 8
??
2014-07-23 09:54:58 [$Zeus$]
đậu má, nộp mãi đc 40 điểm, thì ra là thay cái hàm kiểm tra nguyên tố cùng nhau đi là xong ??????
2014-07-23 06:10:23 Chuyên Nhật CNN
quên không mod thì đc 10 điểm ._.
2014-06-19 18:20:06 Lollipop
for là xong =.=''
2014-06-19 18:18:24 Thcs Ðặng Chánh Kỷ
time khủng vãi
2014-06-19 18:18:08 Lollipop
bài dễ cũng cmt , v~ bạn Đô
2014-06-19 18:17:45 Thcs Ðặng Chánh Kỷ
duyệt trâu 4 for nhớ thêm điều kiện với chia mod cho 10^9 lúc tạo mảng đường đi luôn, mình quên chia lúc tạo mà để chia cuối cùng chỉ được 90
2014-06-19 17:31:48 Thcs Ðặng Chánh Kỷ
nhầm đề, cứ tưởng chỉ đi được 1 ô
2014-06-01 17:06:41 Kraken
đệch! m,n>100 các bác ạ @@!
2014-06-01 16:51:57 Kraken
sao được có 80 nhỉ
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.