首页 > 代码库 > 矩阵运算+快速幂+二分法 poj 3233
矩阵运算+快速幂+二分法 poj 3233
题目链接：http://poj.org/problem?id=3233
思路：矩阵运算，快速幂，二分法。。 妈的 b>>=1 我写成了b>>=2 wrong了一天。 真棒
如何求a+a^2+a^3+ ..... a^n = ?
用二分思想做：我们用S(n/2) = (a+a^2+a^3+...a^n/2);
即 n为奇数时 S(n) = S(n-1) + a^n;
n为偶数时候 S(n) = S(n/2) + S(n/2)*a^n/2;
知道这个就好办了~ 注意细节~。。。。
#include <iostream>#include <cstdio>#include <cstring>using namespace std;int n,m,k;struct Matrix{ int data[31][31]; void init() { memset(data,0,sizeof(data)); for(int i=0;i<=30;i++) data[i][i] = 1; }};Matrix temp;//矩阵乘法 Matrix mul(Matrix a, Matrix b){ Matrix res={{0}} ; for(int i = 0 ; i < n; i++) { for(int j = 0; j < n; j++) { res.data[i][j] = 0; for(int k= 0; k < n; k++) { res.data[i][j] = res.data[i][j] + (a.data[i][k] * b.data[k][j])%m; res.data[i][j] %= m; } } } return res;}//矩阵加法 Matrix add(Matrix a, Matrix b){ Matrix res; res.init(); for(int i = 0 ; i < n; i++) { for(int j = 0; j < n; j++) { res.data[i][j] = a.data[i][j] + b.data[i][j]; res.data[i][j] %= m; } } return res;}//矩阵快速幂 Matrix power(Matrix a, int b){ Matrix res; res.init(); while(b!=0) { if(b%2==1) { res = mul(res,a); } b >>= 1; a = mul(a,a); } return res;}//二分法解决 Matrix solve(int x){ if(x==1) return temp; Matrix res,cur; if(x&1) { res = solve( x - 1); cur=power(temp,x); res=add(res,cur); } else{ cur=power(temp,x/2); res = solve(x/2); res=add(res,mul(cur,res)); } return res;}int main(){ scanf("%d %d %d",&n,&k,&m); //读取 for(int i = 0; i < n;i++) { for(int j = 0;j<n;j++) { scanf("%d",&temp.data[i][j]); } } Matrix s; s = solve(k); for(int i=0;i < n;i++) { for(int j=0;j < n-1;j++) { printf("%d ",s.data[i][j]); } printf("%d\n",s.data[i][n-1]); } return 0;}
矩阵运算+快速幂+二分法 poj 3233
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。