首页 > 代码库 > POJ3233(矩阵二分再二分)
POJ3233(矩阵二分再二分)
题目很有简单:
Description
Given a n × n matrix A and a positive integer k, find the sumS = A + A2 + A3 + … + Ak.
S mod m
范围:n (n ≤ 30), k (k ≤ 109) andm (m < 104).
显然,暴力是不能解决问题,这题目很有意思,而且不会很难想。
我采取的是递归二分求解:
当k 为偶数: 可以化为 (A+ A ^2 +...+A^(k/2) )+A^(k/2)*(A+ A ^2 +...+A^(k/2)) ;
比如 k=6, 就可以化为 (A+A^2+A^3)+(A^3)*(A+A^2+A^3),问题就转化为A+A^2+A^3,之后对A^3进行快速幂乘。
当k为奇数: 可以化为 k-1情况解+ (A^k)
这题目很有意思,就是再求和用了一个二分,在求幂也用了二分。
我写得比较慢,重载了很多符号,强迫症,为了好看。。。。
13577997 | dengyaolong | 3233 | Accepted | 896K | 1672MS | C++ | 2867B | 2014-10-29 17:10:35 |
/*********************************************************** > OS : Linux 3.13.0-24-generic (Mint-17) > Author : yaolong > Mail : dengyaolong@yeah.net > Time : 2014年10月29日 星期三 16时05分45秒 **********************************************************/ #include <iostream> #include <cstdio> #include <string> #include <cstring> using namespace std; struct Matrix { int a[31][31]; int size; int mod; Matrix ( int s, int m ) : size ( s ), mod ( m ) { for ( int i = 1; i <= s; i++ ) { a[i][i] = 1;//单位矩阵 } } Matrix operator * ( const Matrix &rhs ) const //简单的乘法 { Matrix res ( size, mod ); for ( int i = 1; i <= size; i++ ) { for ( int j = 1; j <= size; j++ ) { res.a[i][j] = 0; for ( int k = 1; k <= size; k++ ) { res.a[i][j] = ( res.a[i][j] + ( a[i][k] * rhs.a[k][j] ) ) % mod; } } } return res; } Matrix operator + ( const Matrix &rhs ) const//更简单得加法 { Matrix res ( size, mod ); for ( int i = 1; i <= size; i++ ) { for ( int j = 1; j <= size; j++ ) { res.a[i][j] = ( a[i][j] + rhs.a[i][j] ) % mod; } } return res; } Matrix operator ^ ( int p ) //快速幂 { Matrix r ( size, mod ); Matrix base ( *this ); while ( p ) { if ( p & 1 ) { r = r * base; } base = base * base; p >>= 1; } return r; } void print() //输出 { for ( int i = 1; i <= size; i++ ) { for ( int j = 1; j <= size; j++ ) { if ( j > 1 ) { cout << " "; } cout << a[i][j] ; } cout << endl; } } void input() //输入 { for ( int i = 1; i <= size; i++ ) { for ( int j = 1; j <= size; j++ ) { cin >> a[i][j]; a[i][j] = a[i][j] % mod; } } } }; Matrix PowerPlus ( Matrix m, int k ) { if ( k == 1 ) //只有一时候就直接返回 { return m; } if ( k & 1 ) { Matrix t = PowerPlus ( m, k >> 1 ); return ( m ^ k ) + t + ( m ^ ( k >> 1 ) ) * t ; } else { Matrix t = PowerPlus ( m, k >> 1 ); return t + ( m ^ ( k >> 1 ) ) * t; } } int main() { int size, k, mod; cin >> size >> k >> mod ; Matrix mtr ( size, mod ); mtr.input(); ( PowerPlus ( mtr, k ) ).print(); return 0; }
POJ3233(矩阵二分再二分)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。