题意：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[][];
jz(){ memset(num, , sizeof(num)); }
jz operator*(const jz&p)const
{
jz ans;
for (int k = ; k < ;++k)
for (int i = ; i < ;++i)
for (int j = ; j < ; ++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 = ; i < ; i++)ans.num[i][i] = ;
for (; n;n>>=, x=x*x)
if (n & )ans = ans*x;
return ans;
}
void init()
{
p.num[][] = ; p.num[][] = ; p.num[][] = ;
p.num[][] = ; p.num[][] = ; p.num[][] = ;
p.num[][] = ; p.num[][] = ; p.num[][] = ;
}
int main()
{
ll n;
while (scanf("%lld", &n)!=EOF, n)
{
if (n == ){ printf("0\n"); }
else if (n == ){ printf("1\n"); }
else if (n == ){ printf("2\n"); }
else{
init();
jz ans = POW(p, n - );
printf("%lld\n", (( * ans.num[][]%mod + ans.num[][]))%mod);
}
}
}