首页 > 代码库 > POJ3233:Matrix Power Series(矩阵快速幂+二分）
POJ3233:Matrix Power Series(矩阵快速幂+二分）
http://poj.org/problem?id=3233
题目大意：给定矩阵A，求A + A^2 + A^3 + … + A^k的结果（两个矩阵相加就是对应位置分别相加）。输出的数据mod m。k<=10^9。
这道题两次二分，相当经典。首先我们知道，A^i可以二分求出。然后我们需要对整个题目的数据规模k进行二分。比如，当k=6时，有：
A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3)应用这个式子后，规模k减小了一半。我们二分求出A^3后再递归地计算A + A^2 + A^3，即可得到原问题的答案。
代码如下：
#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <math.h>#include <queue>using namespace std;struct matrix{ int a[31][31];} init,res;int n,k,mod;matrix Mult(matrix x,matrix y){ matrix tmp; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { tmp.a[i][j]=0; for(int k=0; k<n; k++) tmp.a[i][j]=(tmp.a[i][j]+x.a[i][k]*y.a[k][j])%mod; } } return tmp;}matrix Pow(matrix x,int k){ matrix tmp; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) tmp.a[i][j]=(i==j); } while(k) { if(k&1) tmp=Mult(tmp,x); k>>=1; x=Mult(x,x); } return tmp;}matrix Add(matrix x,matrix y){ matrix tmp; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { tmp.a[i][j]=(x.a[i][j]+y.a[i][j])%mod; } } return tmp;}matrix Sum(matrix x,int k){ if(k==1) return x; matrix tmp=Sum(x,k/2),y; if(k&1) { y=Pow(x,k/2+1); tmp=Add(Mult(y,tmp),tmp); return Add(tmp,y); } else { y=Pow(x,k/2); return Add(Mult(y,tmp),tmp); }}int main(){ while(scanf("%d%d%d",&n,&k,&mod)!=EOF) { for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { scanf("%d",&init.a[i][j]); init.a[i][j]%=mod; } } res=Sum(init,k); for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { if(j==0) printf("%d",res.a[i][j]); else printf(" %d",res.a[i][j]); } printf("\n"); } } return 0;}
其他大神的想法：
题目分析：矩阵快速幂。首先我们知道 A^x 可以用矩阵快速幂求出来。其次可以对k进行二分，每次将规模减半，分k为奇偶两种情况，如当k = 6和k = 7时有：
k = 6 有： S(6) = (1 + A^3) * (A + A^2 + A^3) = (1 + A^3) * S(3)。
k = 7 有： S(7) = A + (A + A^4) * (A + A^2 + A^3) = A + (A + A^4) * S(3)。
ps：对矩阵定义成结构体Matrix，求S时用递归，程序会比较直观，好写一点。当然定义成数组，然后再进行一些预处理，效率会更高些。
POJ3233:Matrix Power Series(矩阵快速幂+二分）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。