首页 > 代码库 > POJ 3233 Matrix Power Series(矩阵快速幂+二分)
POJ 3233 Matrix Power Series(矩阵快速幂+二分)
题目地址:POJ 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 <cstdio> #include <string> #include <cstring> #include <stdlib.h> #include <math.h> #include <ctype.h> #include <queue> #include <map> #include <set> #include <algorithm> using namespace std; int mod; int n; struct matrix { int ma[40][40]; }init, res; matrix Mult(matrix x, matrix y) { int i, j, k; matrix tmp; for(i=0;i<n;i++) { for(j=0;j<n;j++) { tmp.ma[i][j]=0; for(k=0;k<n;k++) { tmp.ma[i][j]=(tmp.ma[i][j]+x.ma[i][k]*y.ma[k][j])%mod; } } } return tmp; } matrix Pow(matrix x, int k) { matrix tmp; int i, j; for(i=0;i<n;i++) for(j=0;j<n;j++) tmp.ma[i][j]=(i==j); while(k) { if(k&1) tmp=Mult(tmp,x); x=Mult(x,x); k>>=1; } return tmp; } matrix add(matrix x, matrix y) { int i, j; matrix tmp; for(i=0;i<n;i++) { for(j=0;j<n;j++) { tmp.ma[i][j]=(x.ma[i][j]+y.ma[i][j])%mod; } } return tmp; } matrix sum(matrix x, int k) { matrix tmp; if(k==1) return x; if(k&1) return add(sum(x,k-1),Pow(x,k)); tmp=sum(x,k>>1); return add(tmp,Mult(tmp,Pow(x,k>>1))); } int main() { int k, m, x, i, j; scanf("%d%d%d",&n,&k,&mod); for(i=0;i<n;i++) { for(j=0;j<n;j++) { scanf("%d",&x); init.ma[i][j]=x%mod; } } res=sum(init, k); for(i=0;i<n;i++) { for(j=0;j<n;j++) { printf("%d",res.ma[i][j]); if(j!=n-1) printf(" "); } puts(""); } return 0; }
POJ 3233 Matrix Power Series(矩阵快速幂+二分)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。