fork(1) download
  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
stdin
Standard input is empty
stdout
Standard output is empty