矩阵快速幂 POJ 3070 Fibonacci-白红宇

矩阵快速幂 POJ 3070 Fibonacci

阅读量：5999 次

发布时间：2019-06-20

本文共 1305 字，大约阅读时间需要 4 分钟。

1 /* 2     矩阵快速幂：求第n项的Fibonacci数，转置矩阵都给出，套个模板就可以了。效率很高啊 3 */ 4 #include 
     
       5 #include 
      
        6 #include 
       
         7 #include 
        
          8 using namespace std; 9 10 const int MAXN = 1e3 + 10;11 const int INF = 0x3f3f3f3f;12 const int MOD = 10000;13 struct Mat   {14     int m[2][2];15 };16 17 Mat multi_mod(Mat a, Mat b)   {18     Mat ret;    memset (ret.m, 0, sizeof (ret.m));19     for (int i=0; i<2; ++i) {20         for (int j=0; j<2; ++j) {21             for (int k=0; k<2; ++k) {22                 ret.m[i][j] = (ret.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;23             }24         }25     }26     return ret;27 }28 29 int matrix_pow_mod(Mat x, int n)   {30     Mat ret; ret.m[0][0] = ret.m[1][1] = 1;  ret.m[0][1] = ret.m[1][0] = 0;31     while (n)   {32         if (n & 1)  ret = multi_mod (ret, x);33         x = multi_mod (x, x);34         n >>= 1;35     }36     return ret.m[0][1];37 }38 39 int main(void)  {       //POJ 3070 Fibonacci40     int n;41     while (scanf ("%d", &n) == 1)   {42         if (n == -1)    break;43         Mat x;44         x.m[0][0] = x.m[0][1] = x.m[1][0] = 1; x.m[1][1] = 0;45         printf ("%d\n", matrix_pow_mod (x, n));46     }47 48     return 0;49 }