fork download
copy 
  1. //I_love_coding...
  2. //I_will_win
  3. //I_can_win
  4. //I_must_win
  5. #include<bits/stdc++.h>
  6. using namespace std;
  7. typedef long long int ll;
  8.  
  9. long long int me(long long int x,long long int n,long long int M)
  10. {//(__int128) when needed....
  11.  long long int result=1;
  12.     while(n>0)
  13.     {
  14.         if(n%2==1)
  15.             result=(result*x)%M;  
  16.         x=(x*x)%M;
  17.         n=n/2;
  18.     }
  19.     return result;
  20. }
  21.  
  22.  
  23. //calculates : (1/(a^b))%M;
  24. ll modInverse(ll A,ll B,ll M)
  25. {
  26.     ll k=B*(M-2);
  27.     return me(A,k,M);
  28. }
  29.  
  30.  
  31. int main()
  32. {
  33. 	ios_base::sync_with_stdio(false) ; 
  34. 	cin.tie(NULL);
  35.     cout.tie(NULL);	
  36.     string s;
  37.     cin>>s;
  38.     const int p = 31;
  39.     const int m = 1e9 + 9;
  40.     long long hash_value = 0;
  41.     int n = s.length();
  42.     int hash[n];
  43.     long long p_pow = 1;
  44.     int i=0;
  45.     for (char c : s) 
  46.     {
  47.         hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
  48.         p_pow = (p_pow * p) % m;
  49.         hash[i] = hash_value ; 
  50.         cout<<hash[i]<<"\n";
  51.     i++;
  52.     }
  53.     int i1,j1;
  54.     //s[i1......j1]...
  55.     i1=2;
  56.     j1=4;
  57.     int ans = (hash[j1]%m -hash[i1-1]%m +m)%m;
  58.     int final = (modInverse(p,i1,m) * ans)%m ;     
  59.     cout<<final ;     
  60.         cout<<"\n";
  61.         i1=6;
  62.     j1=8;
  63.      ans = (hash[j1]%m -hash[i1-1]%m +m)%m;
  64.      final = (modInverse(p,i1,m) * ans)%m ;     
  65.     cout<<final ;
  66.  
  67.  
  68. 	return 0;
  69. }
Success #stdin #stdout 0s 4404KB
comments (?)
stdin
copy 
abcecccec
stdout
copy 
1
63
2946
151901
2922464
88809917
751320942
314390255
987479556
3041
3041
https://ideone.com/ClQhjz
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

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!