pku 3070 Fibonacci 矩阵快速幂相乘求Fibonacci 数列-白红宇

pku 3070 Fibonacci 矩阵快速幂相乘求Fibonacci 数列

阅读量：6237 次

发布时间：2019-06-22

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

思路：

这里n很大单纯的递推是O(N)会超时，所以要用矩阵快速幂优化；

f(n) 1 1 f(1)

= 的n-1次方 *

f(n-1) 1 0 f(0)

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a,b) (a) > (b)? (b):(a)#define Max(a,b) (a) > (b)? (a):(b)#define ll __int64#define inf 0x7f7f7f7f#define MOD 10000#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define test puts("<------------------->")#define maxn 10000007#define M 100007#define N 5using namespace std;//freopen("din.txt","r",stdin);struct Mat{ ll mat[3][3]; void init(){ for (int i = 0; i < 2; ++i){ for (int j = 0; j < 2; ++j){ mat[i][j] = 1; } } mat[1][1] = 0; }};Mat operator * (Mat a,Mat b){ Mat c; int i,j,k; CL(c.mat,0); //矩阵乘积 for (i = 0; i < 2; ++i){ for (j = 0; j < 2; ++j){ for (k = 0; k < 2; ++k){ if (!a.mat[i][k] || !b.mat[k][j]) continue; c.mat[i][j] += a.mat[i][k]*b.mat[k][j]; if (c.mat[i][j] > MOD) c.mat[i][j] %= MOD; } } } return c;}Mat operator ^ (Mat a,ll k){ Mat c; int i,j; //单位矩阵 for (i = 0; i < 2; ++i){ for (j = 0; j < 2; ++j){ c.mat[i][j] = (i == j); } } //求k次幂 while (k){ if (k&1) c = c*a; k >>= 1; a = a*a; } return c;}int main(){ ll n; Mat a; while (~scanf("%I64d",&n)){ if (n == -1) break; if (n == 0) {printf("0\n"); continue;} a.init();//初始化 a = (a^(n - 1));//求n - 1次幂的到{fn,fn - 1}; printf("%I64d\n",a.mat[0][0]); } return 0;}