首页 > 代码库 > UVA 10870 Recurrences 矩阵快速幂

UVA 10870 Recurrences 矩阵快速幂

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

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

解题代码:

 1 // File Name: temp.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月17日 星期三 11时35分45秒 4  5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>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;
View Code

 

UVA 10870 Recurrences 矩阵快速幂