ac1248.pas

这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码

program tju1248;
type
  matrix=array[1..2,1..2]of word;
const
  modulo=1729;
  fib:matrix=((0,1),(1,1));
var
  a,b,c:matrix;
  n:cardinal;
procedure matrix_mul(var a,b,c:matrix;m,n,p:byte);
  var
    i,j,k:byte;
  begin
    fillchar(c,sizeof(c),0);
    for i:=1 to m do
      for j:=1 to n do
        for k:=1 to p do
          c[i,k]:=(c[i,k]+a[i,j]*b[j,k]) mod modulo;
  end;
procedure matrix_power(var a,b,c:matrix;n,p:cardinal);
  begin
    if p=1 then
      b:=a
    else if odd(p) then begin
      matrix_power(a,b,c,n,p shr 1);
      matrix_mul(b,b,c,n,n,n);
      matrix_mul(c,a,b,n,n,n);
    end
    else begin
      matrix_power(a,c,b,n,p shr 1);
      matrix_mul(c,c,b,n,n,n);
    end;
  end;
begin
  repeat
    read(n);
    if n<3 then begin writeln(1);continue;end;
    matrix_power(fib,b,a,2,n-2);
    a[1,1]:=1;a[1,2]:=1;
    matrix_mul(a,b,c,1,2,2);
    writeln(c[1,2]);
  until seekeof;
end.