Tribonacci UVA 12470 （简单的斐波拉契数列）（矩阵快速幂）

题意：a1=0;a2=1;a3=2;　　　　a(n)=a(n-1)+a(n-2)+a(n-3); 　　　　求a（n）

思路：矩阵快速幂

#include<cstdio>
#include<cstring>
#define ll long long
#define mod int(1e9+9)
struct jz
{
    ll num[3][3];
    jz(){ memset(num, 0, sizeof(num)); }
    jz operator*(const jz&p)const
    {
        jz ans;
        for (int k = 0; k < 3;++k)
        for (int i = 0; i < 3;++i)
        for (int j = 0; j < 3; ++j)
            ans.num[i][j] = (ans.num[i][j] + num[i][k] * p.num[k][j] % mod) % mod;
        return ans;
    }
}p;
jz POW(jz x, ll n)
{
    jz ans;
    for (int i = 0; i < 3; i++)ans.num[i][i] = 1;
    for (; n;n>>=1, x=x*x)
    if (n & 1)ans = ans*x;
    return ans;
}
void init()
{
    p.num[0][0] = 1; p.num[0][1] = 1; p.num[0][2] = 1;
    p.num[1][0] = 1; p.num[1][1] = 0; p.num[1][2] = 0;
    p.num[2][0] = 0; p.num[2][1] = 1; p.num[2][2] = 0;
}
int main()
{
    ll n;
    while (scanf("%lld", &n)!=EOF, n)
    {
        if (n == 1){ printf("0\n"); }
        else if (n == 2){ printf("1\n"); }
        else if (n == 3){ printf("2\n"); }
        else{
            init();
            jz ans = POW(p, n - 3);
            printf("%lld\n", ((2 * ans.num[0][0]%mod + ans.num[0][1]))%mod);
        }
    }
}