fork(1) 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. int x[2][2];
  12. int **IDENTITY;
  13. int ***st;
  14.  
  15. void f(int sti, int **a, int **b)
  16. {
  17.     for (int i = 0; i < 2; i++)
  18.         for (int j = 0; j < 2; j++)
  19.         {
  20.             for (int k = 0; k < 2; k++)
  21.                 st[sti][i][j] = (st[sti][i][j] + a[i][k] * b[k][j]);
  22.  
  23.             st[sti][i][j] %= r;
  24.         }
  25. }
  26.  
  27. void f1(int sti, int ll, int rr, int ix, int **v)
  28. {
  29.     if (ll == rr)
  30.         f(sti, v, IDENTITY);
  31.     else
  32.     {
  33.         int m = (ll + rr) >> 1;
  34.         if (ix <= m)
  35.             f1(2 * sti + 1, ll, m, ix, v);
  36.         else
  37.             f1(2 * sti + 2, m + 1, rr, ix, v);
  38.  
  39.         f(sti, st[2 * sti + 1], st[2 * sti + 2]);
  40.     }
  41. }
  42.  
  43. int **f2(int sti, int ll, int rr, int lq, int rq)
  44. {
  45.     int **C = new int *[2];
  46.     C[0] = new int[2];
  47.     C[1] = new int[2];
  48.     if (rr < lq || rq < ll)
  49.     {
  50.         C[0][0] = IDENTITY[0][0];
  51.         C[0][1] = IDENTITY[0][1];
  52.         C[1][0] = IDENTITY[1][0];
  53.         C[1][1] = IDENTITY[1][1];
  54.  
  55.         return C;
  56.     }
  57.     else if (lq <= ll && rr <= rq)
  58.     {
  59.         C[0][0] = st[sti][0][0];
  60.         C[0][1] = st[sti][0][1];
  61.         C[1][0] = st[sti][1][0];
  62.         C[1][1] = st[sti][1][1];
  63.  
  64.         return C;
  65.     }
  66.     else
  67.     {
  68.         int m = (ll + rr) >> 1;
  69.         int **A = f2(2 * sti + 1, ll, m, lq, rq);
  70.         int **B = f2(2 * sti + 2, m + 1, rr, lq, rq);
  71.  
  72.         for (int i = 0; i < 2; i++)
  73.             for (int j = 0; j < 2; j++)
  74.             {
  75.                 C[i][j] = 0;
  76.                 for (int k = 0; k < 2; k++)
  77.                     C[i][j] = (C[i][j] + A[i][k] * B[k][j]);
  78.  
  79.                 C[i][j] %= r;
  80.             }
  81.  
  82.         return C;
  83.     }
  84. }
  85.  
  86. signed main()
  87. {
  88.     quicksilver;
  89.     cin >> r >> n >> m;
  90.     IDENTITY = new int *[2];
  91.     IDENTITY[0] = new int[2], IDENTITY[1] = new int[2];
  92.     IDENTITY[0][0] = IDENTITY[1][1] = 1;
  93.     IDENTITY[0][1] = IDENTITY[1][0] = 0;
  94.  
  95.     st = new int **[4 * N];
  96.     for (int i = 0; i < 4 * N; i++)
  97.     {
  98.         st[i] = new int *[2];
  99.         st[i][0] = new int[2], st[i][1] = new int[2];
  100.         st[i][0][0] = st[i][0][1] = st[i][1][0] = st[i][1][1] = 0;
  101.     }
  102.  
  103.     n_ = 1 << (__lg(n) + 1);
  104.     if ((n & (n - 1)) == 0)
  105.         n_ >>= 1;
  106.  
  107.     int **x = new int *[2];
  108.     x[0] = new int[2], x[1] = new int[2];
  109.  
  110.     for (int i = 0; i < n; i++)
  111.     {
  112.         cin >> x[0][0] >> x[0][1] >> x[1][0] >> x[1][1];
  113.  
  114.         f1(0, 0, n_ - 1, i, x);
  115.     }
  116.  
  117.     cout << "\n\n\n";
  118.  
  119.     for (int i = 0; i < m; i++)
  120.     {
  121.         int l, r;
  122.         cin >> l >> r;
  123.         l--, r--;
  124.  
  125.         int **R = new int *[2];
  126.         R[0] = new int[2], R[1] = new int[2];
  127.         int **RT = f2(0, 0, n_ - 1, l, r);
  128.  
  129.         cout << RT[0][0] << ' ' << RT[0][1] << '\n';
  130.         cout << RT[1][0] << ' ' << RT[1][1] << '\n';
  131.         cout << '\n';
  132.     }
  133.  
  134.     return 0;
  135. }
Success #stdin #stdout 0.1s 84836KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy
https://ideone.com/nSlABV
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!