NKPATH - Đường đi trên lưới
Tác giả: ladpro98
Ngôn ngữ: Pascal
program nkpath;
uses math;
const fi='';
maxN=111;
base=trunc(1e9);
var a:array[1..maxN,1..maxN] of longint;
f:array[1..maxN,1..maxN] of longint;
m,n,res:longint;
procedure input;
var inp:text;
i,j:longint;
begin
assign(inp,fi);
reset(inp);
readln(inp,m,n);
for i:=1 to m do
for j:=1 to n do
read(inp,a[i,j]);
close(inp);
end;
function gcd(a,b:longint):longint;
var r: longint;
begin
repeat
r := a mod b;
a := b;
b := r;
until b = 0;
exit(a);
end;
procedure dp;
var i,j,x,y:longint;
begin
for i:=1 to m do
f[i,n]:=1;
for j:=n-1 downto 1 do
for i:=m downto 1 do
begin
for y:=j to n do
for x:=i to m do
if gcd(a[i,j],a[x,y])>1 then
begin
f[i,j]:=(f[i,j]+f[x,y]);
if f[i,j]>=base then dec(f[i,j],base);
end;
end;
end;
procedure output;
var i:longint;
begin
for i:=1 to m do
begin
res:=(res+f[i,1]);
if res>=base then dec(res,base);
end;
write(res);
end;
begin
input;
dp;
output;
end.