题目链接：http://ac.jobdu.com/problem.php?pid=1387

思路：下面是斐波那契额数列的数学公式

利用上面的公式和矩阵快速幂可以在logn的时间复杂度内解决问题。

注：具体矩阵快速幂的思想是怎么样的，可以自己搜索，网上资料很多。

这题当然可以暴力，然后将所有的结果存下来，毕竟只有70组数据，不过这样未免！！！

code:

1 // 斐波那契额数列 2  3 #include 
     
       4 #include 
      
        5 using namespace std; 6 const int M = 2; 7 const int MOD = 1000000007; 8 typedef long long LL; 9 LL ans[M][M];10 LL tmp[M][M];11 12 // 矩阵乘法13 void matrixMul(LL mat1[M][M], LL mat2[M][M])14 {15     LL mat3[M][M];16     for (int i = 0; i < M; ++i)17     {18         for (int j = 0; j < M; ++j)19         {20             mat3[i][j] = 0;21             for (int k = 0; k < M; ++k)22                 mat3[i][j] += mat1[i][k] * mat2[k][j];23         }24     }25     memcpy(mat1, mat3, sizeof(mat3));26 }27 28 // 矩阵快速幂29 void matrixQuickMod(int n)30 {31     tmp[0][0] = 1;32     tmp[0][1] = 1;33     tmp[1][0] = 1;34     tmp[1][1] = 0;35 36     // 将ans处理成单位矩阵37     memset(ans, 0, sizeof(ans));38     for (int i = 0; i < M; ++i) ans[i][i] = 1;39 40     while (n)41     {42         if (n & 1) matrixMul(ans, tmp);        // 当n为奇数时，跟新ans43         n >>= 1;44         matrixMul(tmp, tmp);    // 当n为偶数时跟新tmp45     }46 }47 48 int main()49 {50     int n;51     while (scanf("%d", &n) != EOF)52     {53         matrixQuickMod(n - 1);    54         printf("%lld\n", ans[0][0]);55     }56     return 0;57 }