fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define vi vector<int>
  5. #define v2i vector<vi>
  6. #define v3i vector<v2i>
  7. #define quicksilver ios_base::sync_with_stdio(0), cin.tie(0)
  8.  
  9. const int N = 2e5 + 5;
  10. int r, n, n_, m;
  11. v3i st(4 * N, v2i(2, vi(2, 0)));
  12. v2i IDENTITY(2, vi(2, 0));
  13. v2i C(2, vi(2, 0));
  14. v2i R(2, vi(2, 0));
  15. v2i x(2, vi(2));
  16.  
  17. void f(int sti, v2i a, v2i b)
  18. {
  19. for (int i = 0; i < 2; i++)
  20. for (int j = 0; j < 2; j++)
  21. {
  22. for (int k = 0; k < 2; k++)
  23. st[sti][i][j] = (st[sti][i][j] + a[i][k] * b[k][j]);
  24.  
  25. st[sti][i][j] %= r;
  26. }
  27. }
  28.  
  29. void f1(int sti, int ll, int rr, int ix, v2i v)
  30. {
  31. if (ll == rr)
  32. f(sti, v, IDENTITY);
  33. else
  34. {
  35. int m = (ll + rr) >> 1;
  36. if (ix <= m)
  37. f1(2 * sti + 1, ll, m, ix, v);
  38. else
  39. f1(2 * sti + 2, m + 1, rr, ix, v);
  40.  
  41. f(sti, st[2 * sti + 1], st[2 * sti + 2]);
  42. }
  43. }
  44.  
  45. v2i f2(int sti, int ll, int rr, int lq, int rq)
  46. {
  47. if (rr < lq || rq < ll)
  48. return IDENTITY;
  49. else if (lq <= ll && rr <= rq)
  50. return st[sti];
  51. else
  52. {
  53. int m = (ll + rr) >> 1;
  54. v2i A = f2(2 * sti + 1, ll, m, lq, rq);
  55. v2i B = f2(2 * sti + 2, m + 1, rr, lq, rq);
  56.  
  57. for (int i = 0; i < 2; i++)
  58. for (int j = 0; j < 2; j++)
  59. {
  60. C[i][j] = 0;
  61. for (int k = 0; k < 2; k++)
  62. C[i][j] = (C[i][j] + A[i][k] * B[k][j]);
  63.  
  64. C[i][j] %= r;
  65. }
  66.  
  67. return C;
  68. }
  69. }
  70.  
  71. signed main()
  72. {
  73. quicksilver;
  74. cin >> r >> n >> m;
  75. IDENTITY[0][0] = IDENTITY[1][1] = 1;
  76.  
  77. n_ = 1 << (__lg(n) + 1);
  78. if ((n & (n - 1)) == 0)
  79. n_ >>= 1;
  80.  
  81. for (int i = 0; i < n; i++)
  82. {
  83. cin >> x[0][0] >> x[0][1] >> x[1][0] >> x[1][1];
  84.  
  85. f1(0, 0, n_ - 1, i, x);
  86. }
  87.  
  88. for (int i = 0; i < m; i++)
  89. {
  90. int l, r;
  91. cin >> l >> r;
  92. l--, r--;
  93.  
  94. R = f2(0, 0, n_ - 1, l, r);
  95. cout << R[0][0] << ' ' << R[0][1] << '\n';
  96. cout << R[1][0] << ' ' << R[1][1] << '\n';
  97. cout << '\n';
  98. }
  99.  
  100. return 0;
  101. }
Success #stdin #stdout 0.14s 121708KB
stdin
Standard input is empty
stdout
Standard output is empty