首页 > 代码库 > UVA11149_Power of Matrix
UVA11149_Power of Matrix
题目简洁明了,给出矩阵,求前k次方和。
不知道这种方法是叫做二分幂还是倍增法,如果有知道的,请告诉我一下。
具体思想是这样的,A^1+A^2+A^3+......A^n=(E+A^(n/2))*(A^1+A^2+.....A^(n/2)),如果n为奇数,那么我们只要加上多余的哪一项就可以满足条件了,于是我们就通过这个公式不断的二分下去,用一个矩阵保存左边的矩阵的值,然后右边始终一直二分就可以了,整个复杂度是log^2的。
不过,我看别人的代码都比我跑得快,所以鄙人觉得应该有更简洁的方法,求指教啊。。。。
召唤代码君:
#include <iostream>#include <cstring>#include <cstdio>#define maxn 44using namespace std;int N,m;struct Mat{ int a[44][44]; Mat(){ for (int i=0; i<N; i++) for (int j=0; j<N; j++) a[i][j]=0; } Mat(int x){ for (int i=0; i<N; i++){ for (int j=0; j<N; j++) a[i][j]=0; a[i][i]=1; } } Mat operator + (Mat M0) const { Mat M1; for (int i=0; i<N; i++) for (int j=0; j<N; j++) M1.a[i][j]=(a[i][j]+M0.a[i][j])%10; return M1; } Mat operator * (Mat M0) const { Mat M1; for (int i=0; i<N; i++) for (int j=0; j<N; j++) for (int k=0; k<N; k++) M1.a[i][j]=(M1.a[i][j]+a[i][k]*M0.a[k][j])%10; return M1; } void input(){ for (int i=0; i<N; i++) for (int j=0; j<N; j++) scanf("%d",&a[i][j]),a[i][j]%=10; } void output(){ for (int i=0; i<N; i++){ printf("%d",a[i][0]); for (int j=1; j<N; j++) printf(" %d",a[i][j]); printf("\n"); } printf("\n"); }};Mat power(Mat M,int P){ Mat tot(1); while (P){ if (P&1) tot=tot*M; P>>=1,M=M*M; } return tot;}Mat count(Mat M,int P){ Mat M0,E(1),M1=E; while (P){ if (P&1) M0=M0+M1*power(M,P); P>>=1; M1=M1*(E+power(M,P)); } return M0;}int main(){ Mat M; while (scanf("%d%d",&N,&m) && N!=0){ M.input(); M=count(M,m); M.output(); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。