首页 > 代码库 > POJ 3233 Matrix Power Series
POJ 3233 Matrix Power Series
矩阵快速幂+二分求前n项和
矩阵快速幂是有模板的,多做几道题就会理解,前提是要会快速幂取模;
之所以用二分是因为求和的过程:A^1+A^2...+A^(k-1)+A^k, k是1e9的,所以暴力求和肯定会TLE,在网上找到
了二分求矩阵和的方法;
公式为 (1+A^(k/2))*(A+A^2+..+A^k/2) 的,所以可以写成二分递归,如果k为奇数的话,sum就加上A^k(k为当
前的k值,不再是最初的值),反正是个公式,你要不信的话可以证明一下,所以就贴代码了,感觉到姿势不够优美
呀。
#include <map> #include <cmath> #include <queue> #include <vector> #include <cstdio> #include <string> #include <cstring> #include <iostream> #include <algorithm> #define maxn 50 #define ll long long using namespace std; int n,k,m; struct Matrix { ll v[maxn][maxn]; } matrix; Matrix Mul(Matrix u,Matrix uu) { Matrix c; memset(c.v,0,sizeof(c.v)); for(int i=0; i<m; i++) for(int j=0; j<m; j++) { for(int kk=0; kk<m; kk++) c.v[i][j]+=u.v[i][kk]*uu.v[kk][j]; c.v[i][j]%=k; } return c; } Matrix tul(Matrix A,int t) { Matrix AA=A; Matrix s; memset(s.v,0,sizeof(s.v)); for(int i=0; i<m; i++) s.v[i][i]=1; while(t) { if(t&1) s=Mul(s,AA); t/=2; AA=Mul(AA,AA); } return s; } Matrix pl(Matrix ff,Matrix fff) { for(int i=0; i<m; i++) for(int j=0; j<m; j++) { ff.v[i][j]+=fff.v[i][j]; ff.v[i][j]%=k; } return ff; } Matrix sum(Matrix ff,int dd) { if(dd==1) return ff; Matrix pp; memset(pp.v,0,sizeof(pp.v)); for(int i=0; i<m; i++) pp.v[i][i]=1; pp=pl(pp,tul(ff,dd>>1)); pp=Mul(pp,sum(ff,dd>>1)); if(dd&1) pp=pl(pp,tul(ff,dd)); return pp; } int main() { scanf("%d%d%d",&m,&n,&k); for(int i=0; i<m; i++) for(int j=0; j<m; j++) scanf("%lld",&matrix.v[i][j]); Matrix aa; aa=sum(matrix,n); for(int i=0; i<m; i++) { for(int j=0; j<m; j++) printf("%lld ",aa.v[i][j]%k); cout<<endl; } return 0; }
POJ 3233 Matrix Power Series
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。