fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define ferrario ios_base::sync_with_stdio(0), cin.tie(0)
  6.  
  7. struct matrix
  8. {
  9.     int a, b, c, d;
  10. };
  11.  
  12. const int N = 2e5 + 5;
  13. int r, n, m, n_;
  14. matrix S[4 * N], I;
  15.  
  16. void f1(int sti, int ll, int rr, int ix, const matrix &x)
  17. {
  18.     if (ll == rr)
  19.     {
  20.         S[sti] = x;
  21.     }
  22.     else
  23.     {
  24.         int m = (ll + rr) >> 1;
  25.         if (ix <= m)
  26.             f1(2 * sti + 1, ll, m, ix, x);
  27.         else
  28.             f1(2 * sti + 2, m + 1, rr, ix, x);
  29.  
  30.         S[sti].a = (S[2 * sti + 1].a * S[2 * sti + 2].a + S[2 * sti + 1].b * S[2 * sti + 2].c) % r;
  31.         S[sti].b = (S[2 * sti + 1].a * S[2 * sti + 2].b + S[2 * sti + 1].b * S[2 * sti + 2].d) % r;
  32.         S[sti].c = (S[2 * sti + 1].c * S[2 * sti + 2].a + S[2 * sti + 1].d * S[2 * sti + 2].c) % r;
  33.         S[sti].d = (S[2 * sti + 1].c * S[2 * sti + 2].b + S[2 * sti + 1].d * S[2 * sti + 2].d) % r;
  34.     }
  35. }
  36.  
  37. matrix f2(int sti, int ll, int rr, int lq, int rq)
  38. {
  39.     if (rq < ll || rr < lq)
  40.         return I;
  41.     else if (lq <= ll && rr <= rq)
  42.         return S[sti];
  43.     else
  44.     {
  45.         int m = (ll + rr) >> 1;
  46.         matrix AM = f2(2 * sti + 1, ll, m, lq, rq), BM = f2(2 * sti + 2, m + 1, rr, lq, rq);
  47.         matrix CM;
  48.  
  49.         CM.a = (AM.a * BM.a + AM.b * BM.c) % r;
  50.         CM.b = (AM.a * BM.b + AM.b * BM.d) % r;
  51.         CM.c = (AM.c * BM.a + AM.d * BM.c) % r;
  52.         CM.d = (AM.c * BM.b + AM.d * BM.d) % r;
  53.  
  54.         return CM;
  55.     }
  56. }
  57.  
  58. signed main()
  59. {
  60.     ferrario;
  61.     cin >> r >> n >> m;
  62.     I.a = I.d = 1, I.b = I.c = 0;
  63.     for (int i = 0; i < 4 * N; i++)
  64.         S[i] = I;
  65.  
  66.     n_ = 1 << (__lg(n) + 1);
  67.     if (((n) & (n - 1)) == 0)
  68.         n_ >>= 1;
  69.  
  70.     for (int i = 0; i < n; i++)
  71.     {
  72.         matrix x;
  73.         cin >> x.a >> x.b >> x.c >> x.d;
  74.         f1(0, 0, n_ - 1, i, x);
  75.     }
  76.  
  77.     for (int i = 0; i < m; i++)
  78.     {
  79.         int lx, rx;
  80.         cin >> lx >> rx;
  81.         lx--, rx--;
  82.         matrix rs = f2(0, 0, n_ - 1, lx, rx);
  83.         cout << '\n';
  84.         cout << rs.a << ' ' << rs.b << '\n';
  85.         cout << rs.c << ' ' << rs.d << '\n';
  86.     }
  87.  
  88.     return 0;
  89. }
Success #stdin #stdout 0.01s 28528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/w3Mnl7
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!