[UVA][矩陣 D&C] 12470 - Tribonacci＠Morris' Blog

2012-06-21 14:22:30| 人氣576| 回應0 | 上一篇 | 下一篇

[UVA][矩陣 D&C] 12470 - Tribonacci

推薦 0 收藏 0 轉貼0 訂閱站台

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.

Input

The input contains several test cases (at most 400).

Each test case contains a single integer n (1 ≤ n ≤ 10¹⁶), the desired term in the Tribonacci sequence.

The last line of the input contains a single 0 and should not be processed.

Output

For each test case, output the nth term in the Tribonacci sequence on a single line. This number might be huge, so output the number modulo 1,000,000,009.

Sample input and output

                
                      standard input

                      standard output

                      1
                               2
                               
                               3
                               
                               4
                               
                               5
                               
                               6
                               
                               7
                               
                               8
                               
                               9
                               
                               10
                               
                               100
                               
                               10000
                               
                               10000000
                               
                               100000000000
                               
                               10000000000000000
                               
0                                       
                         
                      0
                               1
                               
                               2
                               
                               3
                               
                               6
                               
                               11
                               
                               20
                               
                               37
                               
                               68
                               
                               125
                               
                               616688122
                               
                               335363379
                               
                               272924536
                               
                               48407255
                               
163452242

作法 : 矩陣 D&C
[1 1 0]
[1 0 1]
[1 0 0]

      [an    an-1 an-2]
A = [an-1 an-2 an-3]
      [an-2 an-3 an-4]

#include <stdio.h>
#define mod 1000000009
struct M {
    long long v[3][3];
} I = {1,0,0,0,1,0,0,0,1},
    o = {0,0,0,0,0,0,0,0,0},
    A = {1,1,0,1,0,1,1,0,0};
void multiply(M &x, M &y) {
    static int i, j, k;
    static M t;
    t = o;
    for(i = 0; i < 3; i++) {
        for(j = 0; j < 3; j++) {
            for(k = 0; k < 3; k++) {
                t.v[i][j] += x.v[i][k]*y.v[k][j];
                t.v[i][j] %= mod;
            }
        }
    }
    x = t;
}
M solve(long long n) {
    M x = I, y = A;
    while(n > 0) {
        if(n&1)
            multiply(x, y);
        n /= 2;
        multiply(y, y);
    }
    return x;
}
int main() {
    long long n;
    while(scanf("%lld", &n) == 1 && n) {
        if(n == 1)
            puts("0");
        else if(n == 2)
            puts("1");
        else if(n == 3)
            puts("2");
        else {
            M res = solve(n-3);
            printf("%lld\n", (res.v[1][0]+res.v[0][0]*2)%mod);
        }
    }
    return 0;
}

我要檢舉

#12470#Tribonacci

台長： Morris

您可能對以下文章有興趣

[UVA] 1260 - Sales

[UVA][SSSP] 523 - Minimum Transport Cost

[UVA][dp] 10559 - Blocks

[UVA] 11047 - The Scrooge Co Problem

人氣(576) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][并查集] 459 - Graph Connectivity
此分類上一篇:[UVA][DP, JAVA] 11375 - Matches

回應(0)

standard input	standard output

1 2 3 4 5 6 7 8 9 10 100 10000 10000000 100000000000 10000000000000000 0	0 1 2 3 6 11 20 37 68 125 616688122 335363379 272924536 48407255 163452242