# Magic Sequence - Kattis

Mar 3rd, 2021 (edited)
695
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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.