Poj3070 Fibonacci — 矩阵乘法+快速幂 求斐波那契数列第N项

Note: 本文最初于 2011年03月25日 星期五 17:04 在 hi.baidu.com/lydrainbowcat 发表。šš

首先，斐波那契数列第N项F[n]=[0,1] * [(0,1), (1,1)]^n

可以利用矩阵乘法及其结合律，用快速幂求出二维矩阵[(0,1), (1,1)]的n次方再乘[0,1]

根据快速幂，把n看做一个二进制数，取出每一位，若该位为1则用一维矩阵f乘二维矩阵，并且每次均对二维矩阵进行自平方。

初值即为第一行中的数值。

Source Code

Problem: 3070		User: lydliyudong
Memory: 844K		Time: 0MS
Language: Pascal		Result: Accepted

• Source Code

type
 matrix=array[1..2,1..2]of longint;
 arr=array[1..2]of longint;
const
 a:matrix=((0,1),(1,1));
var
 f:arr;
 d:matrix;
 n:longint;

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

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

begin
 repeat
  readln(n);
  if n=-1 then break;
  f[1]:=0; f[2]:=1;
  d:=a;
  while n<>0 do
   begin
    if n and 1=1 then f:=f*d;
    d:=d**d;
    n:=n >> 1;
   end;
  writeln(f[1] mod 10000);
 until false;
end.