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.

Download