Advertisement
ismaeil

B. Cryptography2

Jul 24th, 2020
234
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.76 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define Int long long
  3. using namespace std;
  4. #define rg (p << 1) | 1
  5. #define lf (p << 1)
  6.  
  7. vector< vector<Int> > Ans;
  8. int MOD ,n ,m;
  9.  
  10. class SegTree {
  11.     private:
  12.         vector< vector<Int> > Identity ;
  13.         vector< vector< vector<Int> > > Seg;
  14.  
  15.         Int MulMod(Int a ,Int b){
  16.             return 1ll * ( 1ll * (a % MOD) * (b % MOD) ) % MOD;
  17.         }
  18.  
  19.         vector< vector< Int > > Compain(vector< vector< Int > > &a ,vector< vector< Int > > &b) {
  20.  
  21.             vector< vector< Int > > Res(2 ,vector< Int >(2 ,0));
  22.             for(int i = 0 ; i < 2 ; i++)
  23.                 for(int j = 0 ; j < 2 ; j++)
  24.                     for(int k = 0 ; k < 2 ; k++)
  25.                         Res[i][j] += 1ll * MulMod(a[i][k] ,b[k][j]);
  26.             for(int i = 0 ; i < 2 ; i++)
  27.                 for(int j = 0 ; j < 2 ; j++)
  28.                     Res[i][j] %= MOD;
  29.             return Res;
  30.         }
  31.  
  32.         void DoIdentity (){
  33.             Identity.assign(2 ,vector< Int >(2 ,0));
  34.             for(int i = 0 ; i < 2 ; i++)
  35.                 Identity[i][i] = 1ll;
  36.         }
  37.  
  38.         void UPD(int i ,vector< vector< Int > > &v ,int p ,int L ,int R){
  39.             if( i >  R || i <  L ) return;
  40.             if( L == R ) {
  41.                 Seg[p] = v; return;}
  42.  
  43.             int Mid = (L + R) >> 1;
  44.             UPD(i ,v ,lf ,L ,Mid);
  45.             UPD(i ,v ,rg ,Mid + 1 ,R);
  46.             Seg[p] = Compain(Seg[lf] ,Seg[rg]);
  47.         }
  48.  
  49.         vector< vector< Int > > QRY(int i ,int j ,int p ,int L ,int R){
  50.             if( i >  R || L >  j ) return Identity;
  51.             if( i <= L && R <= j ) return Seg[p];
  52.  
  53.             int Mid = (L + R) >> 1;
  54.             vector< vector< Int > > LF = QRY(i ,j ,lf ,L ,Mid);
  55.             vector< vector< Int > > RG = QRY(i ,j ,rg ,Mid + 1 ,R);
  56.             return Compain(LF ,RG);
  57.         }
  58.  
  59.     public:
  60.         SegTree(int n){
  61.             DoIdentity();
  62.             Seg.assign(4 * n ,Identity );
  63.         }
  64.         void UPD(int i ,vector< vector< Int > > &v){
  65.             UPD(i ,v ,1 ,1 ,n);
  66.         }
  67.         vector< vector< Int > > QRY(int L ,int R){
  68.             return QRY(L ,R ,1 ,1 ,n);
  69.         }
  70. };
  71.  
  72. int main() {
  73.     scanf("%d%d%d" ,&MOD ,&n ,&m);
  74.     SegTree ST(n + 1);
  75.  
  76.     vector< vector< Int > > V(2 ,vector< Int >(2));
  77.     for(int idx = 1 ; idx <= n ; idx++){
  78.         for(int i = 0 ; i < 2 ; i++)
  79.             for(int j = 0 ; j < 2 ; j++)
  80.                 scanf("%lld" ,&V[i][j]);
  81.         ST.UPD(idx ,V);
  82.     }
  83.  
  84.     while( m-- ){
  85.             int L ,R; scanf("%d%d" ,&L ,&R);
  86.             Ans = ST.QRY(L ,R);
  87.             for(int i = 0 ; i < 2 ; i++ ,puts(""))
  88.                 for(int j = 0 ; j < 2 ; j++)
  89.                     printf("%lld " ,Ans[i][j]);
  90.             puts("");
  91.     }
  92.     return 0;
  93. }
  94.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement