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.