Advertisement
ismaeil

Magic Sequence

Mar 1st, 2021
686
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.01 KB | None | 0 0
  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.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement