1 #include <cstdio> 2 #include <cstring> 3 const int M = 1E9 + 7; 4 struct Matrix { 5   long long a[2][2]; 6   Matrix() { memset(a, 0, sizeof(a)); } //构造矩阵 7   //定义矩阵乘法 8   Matrix operator * (const Matrix y) {   9     Matrix ans;10     for (int i = 0; i <= 1; ++ i)11       for (int j = 0; j <= 1; ++ j)12         for (int k = 0; k <= 1; ++ k)13           ans.a[i][j] += a[i][k] * y.a[k][j];14     for (int i = 0; i <= 1; ++i)15       for (int j = 0; j <= 1; ++ j)16         ans.a[i][j] %= M;17     return ans;18   }19   //重载等于号20   void operator = (const Matrix b) {21     for (int i = 0; i <= 1; ++i)22       for (int j = 0; j <= 1; ++j)23         a[i][j] = b.a[i][j];24   }25 };26 //矩阵快速幂27 int fast_pow(long long x) {28   Matrix ans, trs;29   ans.a[0][0] = ans.a[1][1] = 1;  //单位矩阵30   trs.a[0][0] = trs.a[1][0] = trs.a[0][1] = 1; //神奇的"斐波那契矩阵"31   //同数字的快速幂一样32   while (x) {33   //若指数为奇数，则用单位矩阵来纪录34     if (x & 1)  35       ans = ans * trs;36     trs = trs * trs;37     x >>= 1;38   }39   //因为最后指数一定会变为1，且矩阵遵守结合律40   //所以开始的单位矩阵在最后就是结果41   return ans.a[0][0];42 }43 int main() {44   int n;45   scanf("%d", &n);46   //结果矩阵左上角是斐波那契数列的第n+1位，所以要算第n-1位47   printf("%d\n", fast_pow(n - 1));48   return 0;49 }