ismaeil

Magic Sequence - Kattis

Mar 3rd, 2021 (edited)
603
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.73 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4.  
  5. typedef pair<ll , string> ls;
  6. #define S second
  7. #define F first
  8.  
  9. const int N = 1e6 + 6e1;
  10. const int M = 64;
  11.  
  12. unordered_map<ll , string> dp;
  13. int n ,cnt1[M] ,cnt2[M];
  14. ll A ,B ,C ,X ,Y;
  15. ls s1[N] ,s2[N];
  16.  
  17. inline int _10(char B64)
  18. {
  19.     if( isdigit(B64) ) return int(B64 - '0');     // 10
  20.     if( isupper(B64) ) return int(B64 - 'A' + 10);// 26
  21.     if( islower(B64) ) return int(B64 - 'a' + 36);// 26
  22.     if( B64 == '{' )   return 62;
  23.     return 63;
  24. }
  25.  
  26. inline string _64(ll x)
  27. {
  28.     if( dp.find(x) != dp.end() ) return dp[x];
  29.        
  30.     string r;
  31.     ll tmpX = x;
  32.    
  33.     do
  34.     {
  35.         char c;
  36.         int m = tmpX % 64;
  37.        
  38.         if( m < 10 )       c = char(m + '0');
  39.         else if( m < 36 )  c = char(m - 10 + 'A');
  40.         else if( m < 62 )  c = char(m - 36 + 'a');
  41.         else if( m == 62 ) c = '{';
  42.         else               c = '|';
  43.        
  44.         r += c;
  45.         tmpX /= 64;
  46.     }
  47.     while( tmpX > 0 );
  48.    
  49.     return dp[x] = r;
  50. }
  51.  
  52. int main()
  53. {
  54.     /// - Require BigO <= O(200000000) == 2s - ///
  55.     /// ---- Cur BigO = O(420005760) > 2s ---- ///
  56.  
  57.     int Tc;
  58.     scanf("%d" ,&Tc);
  59.    
  60.     while( Tc-- )
  61.     {
  62.         /// --- Input --- ///
  63.         scanf("%d" ,&n);
  64.         scanf("%lld%lld%lld" ,&A ,&B ,&C);
  65.         scanf("%lld%lld" ,&X ,&Y);
  66.        
  67.         /// --- Make S[N] --- ///
  68.         s1[0].F = A;
  69.         s1[0].S = _64(A);
  70.         for(int i = 1 ; i < n ; i++)
  71.         {
  72.             s1[i].F = s1[i - 1].F * B;
  73.             s1[i].F %= C;
  74.             s1[i].F += A;
  75.             s1[i].F %= C;
  76.             s1[i].S = _64(s1[i].F);
  77.         }
  78.        
  79.         /// --- Radix Sort --- ///
  80.         for(int d = 0 ; d < 5 ; d++)
  81.         {
  82.             if( d % 2 )
  83.             {
  84.                 for(int i = 0 ; i < n ; i++)
  85.                 {
  86.                     int c = (d < (int)s2[i].S.size()) ? _10(s2[i].S[d]) : 0;
  87.                     cnt2[c] ++;
  88.                 }
  89.                
  90.                 cnt1[0] = 0;
  91.                 for(int c = 1 ; c < 64 ; c++)
  92.                 {
  93.                     cnt2[c] += cnt2[c - 1];
  94.                     cnt1[c] = 0;
  95.                 }
  96.                
  97.                 for(int i = n - 1 ; i >= 0 ; i--)
  98.                 {
  99.                     int c = (d < (int)s2[i].S.size()) ? _10(s2[i].S[d]) : 0;
  100.                     s1[ cnt2[c] - 1 ] = s2[i];
  101.                     cnt2[c] --;
  102.                 }
  103.             }
  104.            
  105.             else
  106.             {
  107.                 for(int i = 0 ; i < n ; i++)
  108.                 {
  109.                     int c = (d < (int)s1[i].S.size()) ? _10(s1[i].S[d]) : 0;
  110.                     cnt1[c] ++;
  111.                 }
  112.                
  113.                 cnt2[0] = 0;
  114.                 for(int c = 1 ; c < 64 ; c++)
  115.                 {
  116.                     cnt1[c] += cnt1[c - 1];
  117.                     cnt2[c] = 0;
  118.                 }
  119.                
  120.                 for(int i = n - 1 ; i >= 0 ; i--)
  121.                 {
  122.                     int c = (d < (int)s1[i].S.size()) ? _10(s1[i].S[d]) : 0;
  123.                     s2[ cnt1[c] - 1 ] = s1[i];
  124.                     cnt1[c] --;
  125.                 }
  126.             }
  127.         }
  128.                
  129.         /// --- Get Hash Value --- ///
  130.         ll V = 0;
  131.         for(int i = 0 ; i < max(n ,64) ; i++)
  132.         {
  133.             if( i < n )
  134.             {
  135.                 V *= X;
  136.                 V %= Y;
  137.                 V += s2[i].F;
  138.                 V %= Y;
  139.             }
  140.            
  141.             if( i < 64 )
  142.             {
  143.                 cnt1[i] = 0;
  144.                 cnt2[i] = 0;
  145.             }
  146.         }
  147.        
  148.         /// --- Output --- ///
  149.         printf("%lld\n" ,V);
  150.     }
  151.    
  152.     return 0;
  153. }
  154.  
Add Comment
Please, Sign In to add comment