Advertisement
ismaeil

Magic Sequence2

Mar 6th, 2021
735
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.94 KB | None | 0 0
  1. /// --- 31623 = O(181960626) --- ///
  2. /// --- Best Base is: Base31623 for (2 digit for 1e9) --- ///
  3.    
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. const int N = 1e6 + 6e1;
  8. const int M = 31623;
  9.  
  10. int n ,cnt1[M] ,cnt2[M];
  11. int s1[N][3] ,s2[N][3] ,R[N];
  12. int a ,b ,c ,x ,y;
  13. bool vs[N];
  14.  
  15. int main()
  16. {  
  17.     int Tc;
  18.     scanf("%d" ,&Tc);
  19.    
  20.     while( Tc-- )
  21.     {
  22.         scanf("%d%d%d%d%d%d" ,&n ,&a ,&b ,&c ,&x ,&y);
  23.        
  24.         s1[0][0] = a;
  25.         s1[0][1] = a % M;
  26.         s1[0][2] = a / M;
  27.        
  28.         int L1 = s1[0][1] ,R1 = s1[0][1];
  29.         int L2 = s1[0][2] ,R2 = s1[0][2];
  30.         for(int i = 1 ; i < n ; i++)
  31.         {
  32.             s1[i][0] = ((1ll * s1[i - 1][0] % c * b % c) % c + a % c) % c;
  33.             s1[i][1] = s1[i][0] % M;
  34.             s1[i][2] = s1[i][0] / M;
  35.  
  36.             L1 = min(L1 ,s1[i][1]);
  37.             R1 = max(R1 ,s1[i][1]);
  38.             L2 = min(L2 ,s1[i][2]);
  39.             R2 = max(R2 ,s1[i][2]);
  40.         }
  41.  
  42.         int K1 = R1 - L1 + 1;
  43.         int K2 = R2 - L2 + 1;
  44.         int K = max(K1 , K2);
  45.        
  46.         /// ----------------------------------------------- ///
  47.        
  48.         for(int i = 0 ; i < n ; i++)
  49.         {
  50.             cnt1[ s1[i][1] - L1 ] ++;
  51.             cnt2[ s1[i][2] - L2 ] ++;
  52.         }
  53.        
  54.         for(int i = 1 ; i < K ; i++)
  55.         {
  56.             if(i < K1) cnt1[i] += cnt1[i - 1];
  57.             if(i < K2) cnt2[i] += cnt2[i - 1];
  58.         }
  59.        
  60.         int j = n - 1;
  61.         for(int i = n - 1 ; i >= 0 ; i--)
  62.         {
  63.             s2[ cnt1[ s1[i][1] - L1 ] - 1 ][0] = s1[i][0];
  64.             s2[ cnt1[ s1[i][1] - L1 ] - 1 ][1] = s1[i][1];
  65.             s2[ cnt1[ s1[i][1] - L1 ] - 1 ][2] = s1[i][2];
  66.             vs[ cnt1[ s1[i][1] - L1 ] - 1 ] = 1;
  67.             cnt1[ s1[i][1] - L1 ] --;
  68.            
  69.             while( vs[j] )
  70.             {
  71.                 R[ cnt2[ s2[j][2] - L2 ] - 1 ] = s2[j][0];
  72.                 cnt2[ s2[j][2] - L2 ] --;
  73.                 j--;
  74.             }
  75.         }
  76.  
  77.         /// ----------------------------------------------- ///
  78.        
  79.         int v = 0;
  80.         for(int i = 0 ; i < max(n ,K) ; i++)
  81.         {
  82.             if( i < n )
  83.             {
  84.                 v = ((1ll * v % y * x % y) % y + R[i] % y) % y;
  85.                 vs[i] = 0;
  86.             }
  87.  
  88.             if( i < K1 ) cnt1[i] = 0;
  89.             if( i < K2 ) cnt2[i] = 0;
  90.         }
  91.        
  92.         printf("%d\n" ,v);
  93.     }
  94.    
  95.     return 0;
  96. }
  97.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement