POJ3233Matrix Power Series(矩阵快速幂)
2018-09-29 03:52:39来源:博客园 阅读 ()
题意
题目链接
给出$n \times n$的矩阵$A$,求$\sum_{i = 1}^k A^i $,每个元素对$m$取模
Sol
考虑直接分治
当$k$为奇数时
$\sum_{i = 1}^k A^i = \sum_{i = 1}^{k / 2 + 1} A^i + A^{k / 2 + 1}(\sum_{i = 1}^{k / 2} A^i)$
当$k$为偶数时
$sum_{i = 1}^k = \sum_{i = 1}^{k / 2} A^i + A^{k / 2}(\sum_{i = 1}^{k / 2}A^i)$
当然还可以按套路对前缀和构造矩阵也是可以做的。
#include<cstdio> #include<cstring> #include<iostream> #include<map> #define LL long long using namespace std; int N, K, mod; int mul(int x, int y) { if(1ll * x * y > mod) return 1ll * x * y % mod; else return 1ll * x * y; } int add(int x, int y) { if(x + y > mod) return x + y - mod; else return x + y; } struct Matrix { int m[31][31]; Matrix() { memset(m, 0, sizeof(m)); } bool operator < (const Matrix &rhs) const { for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) if(m[i][j] != rhs.m[i][j]) return m[i][j] < rhs.m[i][j]; return 1; } Matrix operator * (const Matrix &rhs) const { Matrix ans; for(int k = 1; k <= N; k++) for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) ans.m[i][j] = add(ans.m[i][j], mul(m[i][k], rhs.m[k][j])); return ans; } Matrix operator + (const Matrix &rhs) const { Matrix ans; for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) ans.m[i][j] = add(m[i][j], rhs.m[i][j]); return ans; } }a; Matrix getbase() { Matrix base; for(int i = 1; i <= N; i++) base.m[i][i] = 1; return base; } Matrix fp(Matrix a, int p) { Matrix base = getbase(); while(p) { if(p & 1) base = base * a; a = a * a; p >>= 1; } return base; } Matrix solve(int k) { if(k == 1) return a; Matrix res = solve(k / 2); if(k & 1) { Matrix po = fp(a, k / 2 + 1); return res + po + po * res; } else return res + fp(a, k / 2) * res; } main() { // freopen("a.in", "r", stdin); cin >> N >> K >> mod; for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) cin >> a.m[i][j]; Matrix ans = solve(K); for(int i = 1; i <= N; i++, puts("")) for(int j = 1; j <= N; j++) printf("%d ", ans.m[i][j] % mod); }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 详解并查集 2019-11-02
- POJ2406 Power Strings(KMP) 2018-07-03
- 使用PowerQuery操作OData数据 2018-06-18
- PowerDesigner与UML建模应用 2018-06-18
- PowerDesigner创建物理模型 2018-06-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash