解题报告：

矩阵快速幂。

公式的推理貌似很复杂，官方解题报告没怎么看明白，队友看懂后我就直接按照公式写的。主要是回顾一下构造矩阵的方法和快速幂的精简写法。

最终公式是：F(n) = 5F(n-1) – 7F(n-2) + 4F(n-3)

一共4个参数，那么错开写，一边3个参数，每个参数相差1；如下

F(n - 1)    F(n)

F(n - 2)    F(n - 1)

F(n - 3)    F(n - 2)

然后对于每一对，构造矩阵，例如，

对于第一行的F(n - 1) 和 F(n)，有：

F(n) = 5F(n-1) – 7F(n-2) + 4F(n-3)

写出来就是

5  -7  4   F(n - 1)    F(n)

           F(n - 2)    F(n - 1)

           F(n - 3)    F(n - 2)

对于第二行有F(n - 1) = F(n - 1)

写出来：

5  -7  4   F(n - 1)    F(n)

1  0   0   F(n - 2)    F(n - 1)

           F(n - 3)    F(n - 2)

同理第三行：

5  -7  4   F(n - 1)    F(n)

1  0   0   F(n - 2)    F(n - 1)

0  1   0   F(n - 3)    F(n - 2)

即经过一个矩阵的乘法，可以从n - 1得到n。从F（4）开始，容易得到

5 -7 4                       F(4)          F(n)

1 0  0 的（n - 4）次方 乘以  F(3)   等于   F(n - 1)

0 1  0                       F(2)          F(n - 2)

代码如下：（快速幂部分的写法很经典）

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define mo 9997
int n, ans[3][3], tmp[3][3], x[3][3], e[3][3] = {{5, -7, 4}, {1, 0, 0}, {0, 1, 0}};
int sta[] = {0, 1, 2, 6, 19};
void jeo(int a[][3], int b[][3])
{
    memset(tmp, 0, sizeof(tmp));
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            for(int k = 0; k < 3; k++)
                tmp[i][j] = (tmp[i][j] + (a[i][k] * b[k][j] + mo) % mo + mo) % mo;
    memcpy(b, tmp, sizeof(tmp));
}
void jeogia(int n)
{
    for(;n; n >>= 1)
    {
        if (n & 1) jeo(x ,ans);
        jeo(x, x);
    }
}
int main()
{
    while(scanf("%d", &n) && n)
    {
        if (n <= 4) printf("%d\n", sta[n]);
        else
        {
            memset(ans, 0, sizeof(ans)); ans[0][0] = ans[1][1] = ans[2][2] = 1;
            memcpy(x, e, sizeof(e)); jeogia(n - 4);
            printf("%d\n", ((ans[0][0] * sta[4]) + (ans[0][1] * sta[3]) + (ans[0][2] * sta[2])) % mo);
        }
    }
    return 0;
}