Tính dãy Fibonacci bội 3 với thời gian O(log n)

Dãy Fibonnaci bội 3 có tính chất F(n+3)=F(n+2)+F(n+1)+F(n) n>3.
Đặt
0 0 1
1 0 1 :=A
0 1 1
khi đó ta có [ F(n) F(n+1) F(n+2) ] * A =[F(n+1) F(n+2) F(n+3) ] n>3
=> [ F(n+1) F(n+2) F(n+3) ] = [ F(1) F(2) F(3)] * A ^n= [1 1 1] *A ^n ; n>3

Do các phép toán cộng và nhân được coi là phép toán cơ bản nên ta có thể̉ tính A^n với thời gian O(log n). Từ đó suy ra thuật toán.

PS: Cái giả mã cho giải thuât mọi người tự viết nhá ^^