首页 > 代码库 > 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;
UVA 10870 Recurrences 矩阵快速幂
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。