fork(1) download
copy 
  1. /*
  2.    صل عل محمد
  3.    if (u == Abdel-Aziz Mostafa )   love u <3 ;
  4.   دايما احلم ربنا المنان
  5.  
  6. */
  7. #include<bits/stdc++.h>
  8. #include <ext/pb_ds/assoc_container.hpp>
  9. #include <ext/pb_ds/tree_policy.hpp>
  10.  
  11. using namespace std;
  12.  
  13.  
  14. //#define mod 998244353
  15. #define int long long
  16. #define F first
  17. #define S second
  18.  
  19. string x;
  20. int n  , k;
  21.  
  22. const int N  =  3e6 ;
  23.  
  24. int mod =1e9+7 , p1 ,p2 ,p3;   // 19 , 17 , 256,  257  , 31
  25.  
  26.  
  27.  
  28. #define ll int
  29.  
  30.  
  31. ll random_int(ll l , ll r){
  32.     mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
  33.     return uniform_int_distribution<ll>(l,r)(rng);
  34. }
  35.  
  36. pair< int, pair<int,int> >  Hash[N] , re_Hash[N] ;
  37. int power(int a, int b){
  38.         if(b < 0) return 1;
  39.          int res = 1;
  40.          while(b){
  41.                   if(b & 1) res = res * a % mod;
  42.                   a = a * a % mod;
  43.                   b >>= 1;
  44.          }
  45.          return res;
  46. }
  47. bool prime(int n) {
  48.     if (n <= 1) return false;
  49.     if (n <= 3) return true;
  50.  
  51.     // Check if n is divisible by 2 or 3
  52.     if (n % 2 == 0 || n % 3 == 0) return false;
  53.  
  54.     // Iterate through all numbers from 5 to the square root of n
  55.     for (int i = 5; i * i <= n; i += 6) {
  56.         if (n % i == 0 || n % (i + 2) == 0)
  57.             return false;
  58.     }
  59.  
  60.     return true;
  61. }
  62.  
  63. void pre_hash()            // n * o(power) n * log
  64. {                 //zero based
  65.  
  66.          //   l ....r    << p2 p1 p0
  67.  
  68.             p1=  random_int(33,300);
  69.             p2=random_int(26, 33);
  70.             p3=random_int(250,400);
  71.  
  72.             mod  = random_int(1e9,2e9);
  73.  
  74.             int cnt = 3000 ;
  75.             while(!prime(mod) and cnt--){
  76.                     mod=random_int(1e9 , 2e9);
  77.             }
  78.             if (!prime(mod))
  79.                      mod=  1e9+7;
  80.  
  81.          // int  mod= m ;
  82.  
  83.           for (int i = 0 ; i <n ; ++i){
  84.                    Hash[i].F=Hash[i].S.F = Hash[i].S.S =(x[i]-'a') ;
  85.                    if (i){
  86.                           Hash[i].F   +=   Hash[i-1].F*p1 ;
  87.                           Hash[i].S.F +=  Hash[i-1].S.F*p2 ;
  88.                           Hash[i].S.S +=  Hash[i-1].S.S*p3 ;
  89.                    }
  90.                    Hash[i].F%=mod;
  91.                    Hash[i].S.F%=mod;
  92.                    Hash[i].S.S%=mod;
  93.           }
  94.           for (int i = n-1 ; i >=0 ; --i){       //  p0 p1 p2
  95.                    re_Hash[i].F =re_Hash[i].S.F = re_Hash[i].S.S = x[i]-'a';
  96.                    if (i!=n-1){
  97.                            re_Hash[i].F +=re_Hash[i+1].F * p1;
  98.                            re_Hash[i].S.F +=re_Hash[i+1].S.F *p2;
  99.                            re_Hash[i].S.S +=re_Hash[i+1].S.S *p3;
  100.  
  101.                    }
  102.                    re_Hash[i].F %=mod;
  103.                    re_Hash[i].S.F%=mod;
  104.                    re_Hash[i].S.S%=mod;
  105.           }
  106. }
  107.  
  108. void lets_start_as_we_never_failed(){
  109.  
  110.  
  111.  
  112. }
  113. // 2 :14
  114. signed main() {
  115.  
  116.     ios_base::sync_with_stdio(0);
  117.     cin.tie(0);      cout.tie(0);
  118.  
  119.     int tc=1;
  120.     cin>>tc;
  121.     while(tc--)
  122.         lets_start_as_we_never_failed();
  123.  
  124. }
  125.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/l6wZbq
language:
C++ (gcc 8.3)
created:
233 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!