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.