洛谷P1397 [NOI2013]矩阵游戏(十进制矩阵快速幂)
2018-09-29 03:52:37来源:博客园 阅读 ()
题意
题目链接
Sol
感觉做这题只要对矩阵乘法理解的稍微一点就能做出来
对于每一行构造一个矩阵
A = a 1
0 b
列与列之间的矩阵为
B = c 1
0 d
最终答案为
$A^{n - 1}B A^{n - 1}B \dots $
把$A^{n-1}B$看成一项进行快速幂即可
maya把数据范围看漏了1e6个0。。。。。。。
好像把快速幂换成十进制快速幂就行了
/* 感觉做这题只要对矩阵乘法理解的稍微一点就能做出来 对于每一行构造一个矩阵 A = a 1 0 b 列与列之间的矩阵为 B = c 1 0 d 最终答案为 $A^{n - 1}B A^{n - 1}B$ 把$A^{n-1}B$看成一项进行快速幂即可 maya把数据范围看漏了1e6个0。。。。。。。 好像把快速幂换成十进制快速幂就行了 */ #include<bits/stdc++.h> #define LL long long #define int long long const int MAXN = 1e6 + 10, mod = 1e9 + 7, L = 2; using namespace std; char t1[MAXN], t2[MAXN]; int N[MAXN], M[MAXN], a, b, c, d, n, m; int Mod(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[4][4]; Matrix() { memset(m, 0, sizeof(m)); } Matrix operator * (const Matrix &rhs) const { Matrix ans; /*for(int k = 1; k <= L; k++) for(int i = 1; i <= L; i++) for(int j = 1; j <= L; j++) (ans.m[i][j] += 1ll * m[i][k] * rhs.m[k][j] % mod) %= mod;*/ ans.m[1][1] = add(Mod(m[1][1], rhs.m[1][1]), Mod(m[1][2], rhs.m[2][1])); ans.m[1][2] = add(Mod(m[1][1], rhs.m[1][2]), Mod(m[1][2], rhs.m[2][2])); ans.m[2][1] = add(Mod(m[2][1], rhs.m[1][1]), Mod(m[2][2], rhs.m[2][1])); ans.m[2][2] = add(Mod(m[2][1], rhs.m[1][2]), Mod(m[2][2], rhs.m[2][2])); return ans; } }; Matrix fp(Matrix a, int *p, int len) { Matrix base; for(int i = 1; i <= 3; i++) base.m[i][i] = 1; for(int i = len; i >= 1; i--) { for(int j = 1; j <= p[i]; j++) base = base * a; Matrix tmp = a; a = a * a; a = a * a; a = a * a; a = a * tmp * tmp; } return base; } int trans(char *s, int l, int *to) { for(int i = 1; i <= l; i++) to[i] = s[i] - '0'; to[l]--; for(int i = l; i >= 1; i--) if(to[i] < 0) to[i - 1] += to[i], to[i] = 10 + to[i]; else break; return l; } main() { // freopen("a.in", "r", stdin); scanf("%s%s%d%d%d%d", t1 + 1, t2 + 1, &a, &b, &c, &d); n = strlen(t1 + 1); m = strlen(t2 + 1); n = trans(t1, n, N); m = trans(t2, m, M); Matrix x, y; x.m[1][1] = a; x.m[1][2] = b; x.m[2][1] = 0; x.m[2][2] = 1; y.m[1][1] = c; y.m[1][2] = d; y.m[2][1] = 0; y.m[2][2] = 1; Matrix debug = fp(x, M, m) ; debug = debug * y; Matrix ans = fp(debug, N, n); ans = ans * fp(x, M, m); cout << (ans.m[1][1] + ans.m[1][2]) % mod; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 洛谷P1164->小A点菜 2020-05-18
- 洛谷P1907口算练习题 2020-03-24
- 结题报告--P5551洛谷--Chino的树学 2020-03-13
- 结题报告--洛谷P3915 2020-03-13
- 洛谷P1034 矩形覆盖 2020-03-10
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