PA06ANT - Ant

Tác giả: RR

Ngôn ngữ: Pascal

{$MODE OBJFPC}
{$R+,Q+}
{$M 100111000}

uses math;
const
  FINP='';
  FOUT='';
  ke:array[0..7,0..7] of longint=(
(0,1,0,2,3,0,0,0),
(4,0,5,0,0,6,0,0),
(0,7,0,8,0,0,9,0),
(10,0,11,0,0,0,0,12),
(13,0,0,0,0,14,0,15),
(0,16,0,0,17,0,18,0),
(0,0,19,0,0,20,0,21),
(0,0,0,22,23,0,24,0));

type
  arr=array[1..24,1..24] of int64;

var
  f1,f2:text;
  c:char;
  a,b,p,k:longint;
  un,f:arr;

operator * (a,b:arr) c:arr;
    var
      i,j,k:longint;
    begin
      fillchar(c,sizeof(c),0);
      for i:=1 to 24 do
      for j:=1 to 24 do
          for k:=1 to 24 do
            c[i,j]:=(c[i,j]+a[i,k]*b[k,j]) mod p;
    end;

function lt(k:longint):arr;
    var
      mid:arr;
    begin
      if k=1 then exit(un);
      mid:=lt(k>>1);
      if (k mod 2=1) then exit(mid*mid*un)
      else exit(mid*mid);
    end;

procedure init;
    var
      x,y,z:longint;
    begin
      for x:=0 to 7 do
      for y:=0 to 7 do
      for z:=0 to 7 do
        if (ke[x,y]>0) and (ke[y,z]>0) and (x<>z) then
          un[ke[x,y],ke[y,z]]:=1;
    end;

var
  x,y:longint;
  res:int64;

begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);

  read(f1,c);   a:=ord(c)-ord('A');
  read(f1,c,c); b:=ord(c)-ord('A');
  read(f1,k,p);
  if (k=1) then
    begin
      if (ke[a,b]>0) then writeln(f2,1)
      else writeln(f2,0);
      close(f1); close(f2);
      exit;
    end;

  init;
  f:=lt(k-1);

  for x:=0 to 7 do
  for y:=0 to 7 do
    if (ke[a,x]>0) and (ke[y,b]>0) then
      res:=(res+f[ke[a,x],ke[y,b]]) mod p;

  writeln(f2,res);

  close(f1); close(f2);
end.

Download