经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C » 查看文章
洛谷P1397 [NOI2013]矩阵游戏(十进制矩阵快速幂)
来源:cnblogs  作者:自为风月马前卒  时间:2018/9/26 19:18:32  对本文有异议

题意

题目链接

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。。。。。。。

好像把快速幂换成十进制快速幂就行了

  1. /*
  2. 感觉做这题只要对矩阵乘法理解的稍微一点就能做出来
  3. 对于每一行构造一个矩阵
  4. A = a 1
  5. 0 b
  6. 列与列之间的矩阵为
  7. B = c 1
  8. 0 d
  9. 最终答案为
  10. $A^{n - 1}B A^{n - 1}B$
  11. 把$A^{n-1}B$看成一项进行快速幂即可
  12. maya把数据范围看漏了1e6个0。。。。。。。
  13. 好像把快速幂换成十进制快速幂就行了
  14. */
  15. #include<bits/stdc++.h>
  16. #define LL long long
  17. #define int long long
  18. const int MAXN = 1e6 + 10, mod = 1e9 + 7, L = 2;
  19. using namespace std;
  20. char t1[MAXN], t2[MAXN];
  21. int N[MAXN], M[MAXN], a, b, c, d, n, m;
  22. int Mod(int x, int y) {
  23. if(1ll * x * y > mod) return 1ll * x * y % mod;
  24. else return 1ll * x * y;
  25. }
  26. int add(int x, int y) {
  27. if(x + y > mod) return x + y - mod;
  28. else return x + y;
  29. }
  30. struct Matrix {
  31. int m[4][4];
  32. Matrix() {
  33. memset(m, 0, sizeof(m));
  34. }
  35. Matrix operator * (const Matrix &rhs) const {
  36. Matrix ans;
  37. /*for(int k = 1; k <= L; k++)
  38. for(int i = 1; i <= L; i++)
  39. for(int j = 1; j <= L; j++)
  40. (ans.m[i][j] += 1ll * m[i][k] * rhs.m[k][j] % mod) %= mod;*/
  41. ans.m[1][1] = add(Mod(m[1][1], rhs.m[1][1]), Mod(m[1][2], rhs.m[2][1]));
  42. ans.m[1][2] = add(Mod(m[1][1], rhs.m[1][2]), Mod(m[1][2], rhs.m[2][2]));
  43. ans.m[2][1] = add(Mod(m[2][1], rhs.m[1][1]), Mod(m[2][2], rhs.m[2][1]));
  44. ans.m[2][2] = add(Mod(m[2][1], rhs.m[1][2]), Mod(m[2][2], rhs.m[2][2]));
  45. return ans;
  46. }
  47. };
  48. Matrix fp(Matrix a, int *p, int len) {
  49. Matrix base;
  50. for(int i = 1; i <= 3; i++) base.m[i][i] = 1;
  51. for(int i = len; i >= 1; i--) {
  52. for(int j = 1; j <= p[i]; j++) base = base * a;
  53. Matrix tmp = a;
  54. a = a * a; a = a * a; a = a * a; a = a * tmp * tmp;
  55. }
  56. return base;
  57. }
  58. int trans(char *s, int l, int *to) {
  59. for(int i = 1; i <= l; i++) to[i] = s[i] - '0';
  60. to[l]--;
  61. for(int i = l; i >= 1; i--)
  62. if(to[i] < 0) to[i - 1] += to[i], to[i] = 10 + to[i];
  63. else break;
  64. return l;
  65. }
  66. main() {
  67. // freopen("a.in", "r", stdin);
  68. scanf("%s%s%d%d%d%d", t1 + 1, t2 + 1, &a, &b, &c, &d);
  69. n = strlen(t1 + 1); m = strlen(t2 + 1);
  70. n = trans(t1, n, N); m = trans(t2, m, M);
  71. Matrix x, y;
  72. x.m[1][1] = a; x.m[1][2] = b;
  73. x.m[2][1] = 0; x.m[2][2] = 1;
  74. y.m[1][1] = c; y.m[1][2] = d;
  75. y.m[2][1] = 0; y.m[2][2] = 1;
  76. Matrix debug = fp(x, M, m) ;
  77. debug = debug * y;
  78. Matrix ans = fp(debug, N, n);
  79. ans = ans * fp(x, M, m);
  80. cout << (ans.m[1][1] + ans.m[1][2]) % mod;
  81. }

 

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号