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

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      z=1000000000;
      maxn=101;
var n,m,re:longint;
    a,f:array[1..maxn,1..maxn] of longint;

procedure rf;
var i,j:longint;
begin
     readln(m,n);
     for i:=1 to m do
         for j:=1 to n do
             read(a[i,j]);
end;

function gcd(x,y:longint):boolean;
begin
     gcd:=true;
     if x*y=0 then
     begin
          gcd:=(x+y)<>1;
          exit;
     end;
     if (x and 1) or (y and 1)=0 then exit;
     if x>y then gcd:=gcd(x mod y,y)
     else gcd:=gcd(x,y mod x);
end;

procedure pr;
var i,j,u,v:longint;
begin
     for i:=1 to m do f[i,1]:=1;
     for j:=1 to n do
         for i:=1 to m do
         begin
              for v:=1 to j-1 do
                  for u:=1 to i do
                      if gcd(a[i,j],a[u,v]) then
                      begin
                           f[i,j]:=f[i,j]+f[u,v];
                           if f[i,j]>=z then f[i,j]:=f[i,j]-z; 
                      end;
              if j<n then
                 for u:=1 to i-1 do
                     if gcd(a[i,j],a[u,j]) then
                     begin
                          f[i,j]:=f[i,j]+f[u,j];
                          if f[i,j]>=z then f[i,j]:=f[i,j]-z;
                     end;
         end;
end;

procedure wf;
var i:longint;
begin
     re:=0;
     for i:=1 to m do
     begin
          re:=re+f[i,n];
          if re>=z then re:=re-z;
     end;
     writeln(re);
end;

begin
     assign(input,fi); reset(input);
     assign(output,fo); rewrite(output);
     rf;
     pr;
     wf;
     close(input); close(output);
end.

Download