首页 > 代码库 > HDU 4965 矩阵快速幂
HDU 4965 矩阵快速幂
顺手写了下矩阵类模板
利用到矩阵乘法的交换律 (A*B)^n == A * (B*A)^n-1 *B
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <utility>#include <stack>#include <queue>#include <map>#include <deque>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))#define INF 0x3f3f3f3f#define MOD 6using namespace std;int n,m;struct Matrix{ int n,m; vector< vector<int> >a; Matrix(){}; Matrix(const Matrix & T) : n(T.n),m(T.m) { a.resize(n); for(int i=0; i<n; i++) { a[i].resize(m); for(int j=0; j<m; j++) a[i][j]=T.a[i][j]; } } Matrix(int N, int M) { n=N; m=M; a.resize(N); for(int i=0; i<N; i++) a[i].resize(M); } Matrix & operator=(const Matrix &T) { n=T.n; m=T.m; a.resize(n); for(int i=0; i<n; i++) { a[i].resize(m); for(int j=0; j<m; j++) a[i][j]=T.a[i][j]; } return *this; } Matrix operator+(const Matrix &T) const { Matrix tmp(n,m); for(int i=0; i<n; i++) for(int j=0; j<m; j++) tmp.a[i][j]=a[i][j]+T.a[i][j]; return tmp; } Matrix operator*(const Matrix &T) const { Matrix tmp(n,T.m); for(int i=0; i<n; i++) for(int j=0; j<T.m; j++) for(int k=0; k<m; k++) tmp.a[i][j]=(tmp.a[i][j]+a[i][k]*T.a[k][j])%MOD; return tmp; } void input(int N, int M) { n=N; m=M; a.resize(n); for(int i=0; i<n; i++) { a[i].resize(m); for(int j=0; j<m; j++) scanf("%d",&a[i][j]); } } void output() { for(int i=0; i<n; i++) { for(int j=0; j<m; j++) printf("%d ",a[i][j]); printf("\n"); } } Matrix pow_m(int N)//矩阵满足n=m { Matrix ret(n,n),tmp(*this); for(int i=0; i<n; i++) ret.a[i][i]=1; while(N) { if(N&1) ret=ret*tmp; tmp=tmp*tmp; N>>=1; } return ret; }};int main(){ while(scanf("%d%d",&n,&m)!=EOF && n && m) { Matrix a,b,c,d; a.input(n,m); b.input(m,n); c=b*a; d=c.pow_m(n*n-1); d=a*d*b; int ans=0; for(int i=0; i<d.n; i++) for(int j=0; j<d.m; j++) ans=ans+d.a[i][j]; printf("%d\n",ans); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。