首页 > 代码库 > 【poj3233】 Matrix Power Series
【poj3233】 Matrix Power Series
http://poj.org/problem?id=3233 (题目链接)
题意:给出一个n×n的矩阵A,求模m下A+A2+A3+…+Ak 的值
Solution
今日考试就A了这一道题。。
当k为偶数时,原式=(Ak2+1)×(A1+A2+...+Ak2)
当k为奇数的时候将Ak乘上当前答案后抠出去,最后统计答案时再加上。所以我们就一路快速幂搞过去,AC
代码:
// poj3233#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=31;int A[maxn][maxn],B[maxn][maxn],C[maxn][maxn],T[maxn][maxn],tmp[maxn][maxn],ans[maxn][maxn],D[maxn][maxn];int n,m;void pow(int k) { for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) B[i][j]=0,T[i][j]=A[i][j]; B[i][i]=1; } while (k) { if (k&1) { for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { tmp[i][j]=0; for (int k=1;k<=n;k++) tmp[i][j]=(tmp[i][j]+B[i][k]*T[k][j])%m; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) B[i][j]=tmp[i][j]; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { C[i][j]=0; for (int k=1;k<=n;k++) C[i][j]=(C[i][j]+T[i][k]*T[k][j])%m; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) swap(C[i][j],T[i][j]); k>>=1; }}void update() { for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { tmp[i][j]=0; for (int k=1;k<=n;k++) tmp[i][j]=(tmp[i][j]+ans[i][k]*B[k][j])%m; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) ans[i][j]=tmp[i][j];}int main() { int k; scanf("%d%d%d",&n,&k,&m); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) scanf("%d",&A[i][j]); memset(ans,0,sizeof(ans));for (int i=1;i<=n;i++) ans[i][i]=1; while (k>1) { if (k&1) { for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) T[i][j]=A[i][j]; pow(k); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { tmp[i][j]=0; for (int k=1;k<=n;k++) tmp[i][j]=(tmp[i][j]+B[i][k]*ans[k][j])%m; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) D[i][j]=(D[i][j]+tmp[i][j])%m; } pow(k/2); for (int i=1;i<=n;i++) B[i][i]=(B[i][i]+1)%m; update(); k>>=1; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) B[i][j]=A[i][j]; update(); for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) printf("%d ",(ans[i][j]+D[i][j])%m); printf("\n"); } return 0;}
【poj3233】 Matrix Power Series
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。