题意：公式f(n) = f(n - 1) + f(n - 2) + f(n - 3)，给出n，f(1) = 0，f(2) = 1， f(3) = 2，要求得出f(n)。
题解：普通的矩阵快速幂模板题。

#include 
   
     #include 
    
      const int MOD = 1000000009; struct Mat { long long g[3][3]; }ori, res; long long n; Mat multiply(Mat x, Mat y) { Mat temp; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) { temp.g[i][j] = 0; for (int k = 0; k < 3; k++) temp.g[i][j] = (temp.g[i][j] + x.g[i][k] * y.g[k][j]) % MOD; } return temp; } void calc(long long n) { while (n) { if (n & 1) ori = multiply(ori, res); n >>= 1; res = multiply(res, res); } } int main() { while (scanf("%lld", &n) && n) { if (n == 1 || n == 2 || n == 3) { printf("%lld\n", n - 1); continue; } memset(ori.g, 0, sizeof(ori)); memset(res.g, 0, sizeof(res)); ori.g[0][0] = 2; ori.g[0][1] = 1; ori.g[0][2] = 0; res.g[0][0] = res.g[1][0] = res.g[2][0] = 1; res.g[0][1] = res.g[1][2] = 1; calc(n - 3); printf("%lld\n", ori.g[0][0]); } return 0; }