UVa 12470 -- Tribonacci

Key: Linear algebra

http://en.wikipedia.org/wiki/Recurrence_relation

http://en.wikipedia.org/wiki/Companion_matrix



原問題：

Problem J. Tribonacci

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. Got it?

Leonardo Pisano Bigollo 
13th Century

Everybody knows about Fibonacci, they guy who invented the famous sequence where the first two terms are 0 and 1 and from then on every term is the sum of the previous two.

What most people don’t know is that he had a somewhat mentally retarded brother named Tribonacci. In a desperate attempt to surpass his brother and achieve eternal glory, Tribonacci invented his own sequence: the first three terms are 0, 1, 2 and from then on every term is the sum of the previous three.

Sadly, regardless of enormous courage and dedication, Tribonacci was never able to compute more than the first 3 terms of his sequence. Even more sadly, one cold night he performed an extraordinary mental effort that dilated one of the blood vessels in his brain, causing severe hemorrhage and killing him instantly. This is clinically known as an aneurysm, but of course Tribonacci did not know this (it is suspected that even pronouncing the word aneurysm would have been an impossible task for him).

Write a program that changes history and finds the nth term in the Tribonacci sequence modulo 1,000,000,009.

1,000,000,009 這數字是有意義的，因為這是個質數，取 mod 之後，

幾乎很難誤打誤撞瞎到正確答案。

因為是寫程式，所以計算高次方矩陣不能傻傻的算，

要用已知的訊息加速，這樣可以把單純 O(n) 算法降到 O(log n)。

((說不定有人覺得 O(log n) 算法也很單純))

總之，類似題 UVa 10689 - Yet another Number Sequence

還有一種是故意問你很大的 Fibonacci number，

此時可以開 array 簡單模擬大數，畢竟 Fibonacci sequence 只是簡單的加法運算。