UVA 10870 Recurrences 矩阵快速幂-白红宇

UVA 10870 Recurrences 矩阵快速幂

阅读量：5116 次

发布时间：2019-06-13

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

题意：给你递推公式要求矩阵快速幂的第n项

解题思路：经典的矩阵快速幂递推第n项目做法。

解题代码：

1 // File Name: temp.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月17日 星期三 11时35分45秒 4  5 #include
      
        6 #include
       
         7 #include
         8 #include
         
           9 #include
          
           10 #include
           
            11 #include
            
             12 #include
             
              13 #include
              
               14 #include
               
                15 #include
                
                 16 #include
                 
                  17 #include
                  
                   18 #include
                   
                    19 #include
                    
                     20 #include
                     
                      21 #include
                      
                       22 #include
                       
                        23 #include
                        
                         24 #define LL long long25 using namespace std;26 LL n ,m , d; 27 int ta,tb;28 struct Matrix29 {30 LL mat[15][15];31 void clear()32 {33 memset(mat,0,sizeof(mat));34 }35 void output()36 {37 for(int i = 0 ;i < n ;i ++)38 {39 for(int j = 0 ;j < n ;j ++)40 printf("%lld ",mat[i][j]);41 printf("\n");42 }43 }44 void init()45 {46 clear();47 for(int i = 0 ;i < n;i ++ )48 {49 scanf("%lld",&mat[0][i]);50 mat[0][i] %= m ; 51 }52 for(int i = 1;i < n;i ++)53 {54 mat[i][i-1] =1; 55 }56 }57 Matrix operator *(const Matrix &b) const58 {59 Matrix ret;60 ret.clear();61 for(int i = 0 ;i < n ;i ++)62 for(int j = 0;j < n;j ++)63 {64 for(int s = 0 ;s < n ;s ++)65 {66 ret.mat[i][j] =(ret.mat[i][j] + mat[i][s] * b.mat[s][j]) %m ; // 第I 行 第J 列 67 }68 }69 return ret;70 }71 };72 Matrix Pow( Matrix a ,LL t )73 {74 Matrix ret;75 ret.clear();76 for(int i = 0 ;i < n ;i ++)77 ret.mat[i][i] = 1;78 Matrix tmp = a; 79 while(t)80 {81 if(t&1) ret = ret * tmp;