首页 > 代码库 > poj3233 Matrix Power Series 矩阵快速幂
poj3233 Matrix Power Series 矩阵快速幂
题目链接:
http://poj.org/problem?id=3233
题意:
给你A矩阵,A矩阵是n*n的一个矩阵,现在要你求S = A + A^2 + A^3 + … + A^k.
那么s一定也是一个N*N的矩阵,最后要你输出s,并且s的每一个元素对m取余数
思路:
令Sk-1=I+A+A^2+.....+A^(k-1)
则Sk=I+A+A^2+.....+A^k+A^k
所以 Sk=Sk-1+A^k
答案就是 mat[i+n][j]
代码:
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <cstdio> 5 using namespace std; 6 typedef long long ll; 7 #define MS(a) memset(a,0,sizeof(a)) 8 #define MP make_pair 9 #define PB push_back 10 const int INF = 0x3f3f3f3f; 11 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 12 inline ll read(){ 13 ll x=0,f=1;char ch=getchar(); 14 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 15 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 16 return x*f; 17 } 18 ////////////////////////////////////////////////////////////////////////// 19 const int maxn = 1e5+10; 20 21 int n,k,mod; 22 struct node{ 23 int mat[65][65]; 24 }ans,cnt; 25 26 node mul(node a,node b){ 27 int t = n*2; 28 node re; 29 memset(re.mat,0,sizeof(re.mat)); 30 for(int i=0; i<t; i++) 31 for(int k=0; k<t; k++) 32 for(int j=0; j<t; j++) 33 re.mat[i][j] = (re.mat[i][j]+a.mat[i][k]*b.mat[k][j])%mod; 34 35 return re; 36 } 37 38 void qpow(int k){ 39 while(k){ 40 if(k & 1) ans = mul(ans,cnt); 41 cnt = mul(cnt,cnt); 42 k >>= 1; 43 } 44 } 45 46 int main(){ 47 while(cin>>n>>k>>mod){ 48 memset(cnt.mat,0,sizeof(cnt.mat)); 49 memset(ans.mat,0,sizeof(ans.mat)); 50 for(int i=0; i<n; i++) 51 for(int j=0; j<n; j++){ 52 cnt.mat[i][j] = read(); 53 cnt.mat[i+n][j] = cnt.mat[i][j]; 54 } 55 56 for(int i=0; i<n; i++){ 57 cnt.mat[i+n][i+n] = 1; 58 ans.mat[i][i] = ans.mat[i+n][i+n] = 1; 59 } 60 61 qpow(k); 62 63 for(int i=0; i<n; i++){ 64 for(int j=0; j<n; j++){ 65 printf("%d ",ans.mat[i+n][j]); 66 } 67 puts(""); 68 } 69 } 70 71 return 0; 72 }
poj3233 Matrix Power Series 矩阵快速幂
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。