fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eZXWMF
language:
C++14 (gcc 8.3)
created:
1 year 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!