Advertisement
Guest User

Untitled

a guest
Apr 21st, 2019
169
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.36 KB | None | 0 0
  1. //idiot_owl IIITA
  2. #include<bits/stdc++.h>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. #define ll long long int
  7. #define pll pair<ll,ll>
  8. #define pii pair<int,int>
  9. #define fi first
  10. #define se second
  11. #define mp make_pair
  12. #define pb push_back
  13. #define all(a) (a).begin(),(a).end()
  14. #define s(x) scanf("%d",&x)
  15. #define sll(x) scanf("%lld",&x)
  16. #define pf(x) printf("%d\n",x)
  17. #define pfl(x) printf("%lld\n",x)
  18. #define flash ios_base::sync_with_stdio(false);cin.tie(0)
  19. #define goog(x) cout << "Case #" << x << ": "
  20. #define MAX5 100005
  21. #define MAX6 1000005
  22. #define MLOG 18
  23. #define limit 1e18
  24. #define mod 1000000007
  25. #define mod2 998244353
  26.  
  27. typedef tree<
  28. int,
  29. null_type,
  30. less<int>,
  31. rb_tree_tag,
  32. tree_order_statistics_node_update>
  33. ordered_set;
  34. const ll Rval1DOM = chrono::high_resolution_clock::now().time_since_epoch().count();
  35. struct chash {
  36.     ll operator()(pair<ll,ll> x) const { return (x.fi ^ Rval1DOM + x.se^Rval1DOM); }
  37. };
  38. #define ht gp_hash_table<pair<ll,ll>, ll, chash>
  39.  
  40. ll power(ll x, ll y, ll p){
  41.     ll res = 1;
  42.     x = x % p;
  43.     while (y > 0){
  44.         if (y & 1)
  45.             res = (res*x) % p;
  46.         y = y>>1;
  47.         x = (x*x) % p;
  48.     }
  49.     return res;
  50. }
  51. ht m;
  52. int arr[20003];
  53. ll p = 33179, p2 = 33179;
  54. int main(){
  55.     int n;
  56.     cin >> n;
  57.     for(int i = 0; i < n; i++){
  58.         cin >> arr[i];
  59.         arr[i]++;
  60.     }
  61.     for(int i = 0; i < n; i++){
  62.         arr[i+n] = arr[i];
  63.     }
  64.     int ind = 0;
  65.     ll d = 33;
  66.     ll h1 = 0, h2 = 0;
  67.     string s;
  68.     for(int i = 0; i < n; i++){
  69.         h1 = 0;
  70.         h2 = 0;
  71.         s = "";
  72.         for(int j = i; j < i+n; j++){
  73.             d = ((arr[j])*power(p,j-i+1,mod))%mod;
  74.             h1 = (h1 + d)%mod;
  75.             d = ((arr[j])*power(p2,j-i+1,mod2))%mod2;
  76.             h2 = (h2 + d)%mod2;
  77.             s += (arr[j] + '0');
  78.             m[{h1, h2}]++;
  79.         }
  80.     }
  81.     reverse(arr, arr+2*n);
  82.     for(ll i = 0; i < n; i++){
  83.         h1 = 0;
  84.         h2 = 0;
  85.         for(ll j = i; j < i+n; j++){
  86.             d = ((arr[j])*power(p,j-i+1,mod))%mod;
  87.             h1 = (h1 + d)%mod;
  88.             d = ((arr[j])*power(p2,j-i+1,mod2))%mod2;
  89.             h2 = (h2 + d)%mod2;
  90.             m[{h1, h2}]++;
  91.         }
  92.     }
  93.     int cnt = 0;
  94.     for(auto it = m.begin(); it != m.end(); it++){
  95.         cnt++;
  96.     }
  97.     cout << cnt << endl;
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement