ismaeil

Magic Sequence

Mar 1st, 2021
507
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FastIO cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
  5. #define LSOne(a) ( (a) & -(a) )
  6. #define SQ(a) (a)*(a)
  7. #define INF      4e18
  8. #define EPS      1e-9
  9. #define OO        1e9
  10. #define PB  push_back
  11. #define MP  make_pair
  12. #define S      second
  13. #define F       first
  14.  
  15. typedef long double     ld;
  16. typedef long long       ll;
  17. typedef pair<int , int> ii;
  18. typedef pair<int , ii> iii;
  19. typedef pair<ll , ll>  pll;
  20. typedef vector< int >   vi;
  21. typedef vector< ll >    vl;
  22. typedef vector< ii >   vii;
  23. typedef vector< pll >  vll;
  24.  
  25. /// ======================= ///
  26.  
  27. string Read(bool spaces)
  28. {
  29.     const int MaxN = 2e6 + 1;
  30.     static char Buff[MaxN];
  31.    
  32.     fflush(stdin);
  33.     fflush(stdout);
  34.     spaces ? scanf("%[^\n]s" ,Buff)
  35.            : scanf("%s" ,Buff);
  36.     fflush(stdin);
  37.     fflush(stdout);
  38.    
  39.     return Buff;
  40. }
  41.  
  42. /// ======================= ///
  43. typedef tuple<int ,string ,int> is;
  44.  
  45. const ll  MOD = 1e9 + 7;
  46. const int N = 1e6 + 6e1;
  47. int n ,a ,b ,c ,x ,y;
  48. vector< is > s ,tmpS;
  49. vector< vi > cnt;
  50.  
  51. inline int getDec(char _64)
  52. {
  53.     if( isdigit(_64) ) return (int)_64 - '0';
  54.     if( 'a' <= _64 && _64 <= 'z' ) return (int)_64 - 'a' + 10;
  55.     return (int)_64 - 'A' + 36;
  56. }
  57.  
  58. inline string get64(int dc)
  59. {
  60.     string r;
  61.     while( dc )
  62.     {
  63.         int m = dc % 64;
  64.        
  65.         if( m < 10 )
  66.             r += char(m + '0');
  67.         else if( m < 36 )
  68.             r += char(m - 10 + 'a');
  69.         else
  70.             r += char(m - 36 + 'A');
  71.        
  72.         dc /= 64;
  73.     }
  74.     return r;
  75. }
  76.  
  77. void makeS()
  78. {
  79.     ll num = a;
  80.     string B = get64(a);
  81.     int sz  =  B.size();
  82.    
  83.     s.resize(n);
  84.     tmpS.resize(n);
  85.     s[0] = is(num ,B ,sz);
  86.     for(int i = 1 ; i < n ; i++)
  87.     {
  88.         num = get<0>(s[i - 1]);
  89.         num %= c;
  90.         num *= 1ll * b;
  91.         num %= c;
  92.         num += a;
  93.         num %= c;
  94.        
  95.         B = get64(num);
  96.         sz  = B.size();
  97.         s[i] = is(num ,B ,sz);
  98.     }
  99. }
  100.  
  101. void RadixSort()
  102. {
  103.     int dc ,i ,j ,k ,v ,f = 1;
  104.     for(int d = 0 ; f ; d += 1)
  105.     {
  106.         f = 0;
  107.         cnt.assign(64 ,vi());
  108.         for(i = 0 ; i < n ; i++)
  109.         {
  110.             dc = 0;
  111.             if( d < get<2>(s[i]) )
  112.             {
  113.                 f = 1;
  114.                 dc = getDec( get<1>(s[i])[d] );
  115.             }
  116.             cnt[dc].PB(i);
  117.             tmpS[i] = s[i];
  118.         }
  119.        
  120.         if( !f ) break;
  121.         k = 0;
  122.         for(v = 0 ; v < 64 ; v++)
  123.             for(j = 0 ; j < (int)cnt[v].size() ; j++)
  124.                 s[k++] = tmpS[cnt[v][j]];
  125.     }
  126. }
  127.  
  128. ll getHash()
  129. {
  130.     ll v = 0;
  131.     for(is i : s)
  132.     {
  133.         v *= 1ll * x;
  134.         v %= y;
  135.         v += get<0>(i);
  136.         v %= y;
  137.     }
  138.     return v;
  139. }
  140.  
  141. void Solve()
  142. {
  143.     scanf("%d%d%d%d%d%d" ,&n ,&a ,&b ,&c ,&x ,&y);
  144.    
  145.     makeS();
  146.     RadixSort();
  147.    
  148.     printf("%lld\n" ,getHash());
  149. }
  150.  
  151. int main()
  152. {
  153.     int Tc; scanf("%d" ,&Tc);
  154.     while( Tc-- ) Solve();
  155.     return 0;
  156. }
  157.  
  158.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×