Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //idiot_owl IIITA
- #include<bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- #define ll long long int
- #define pll pair<ll,ll>
- #define pii pair<int,int>
- #define fi first
- #define se second
- #define mp make_pair
- #define pb push_back
- #define all(a) (a).begin(),(a).end()
- #define s(x) scanf("%d",&x)
- #define sll(x) scanf("%lld",&x)
- #define pf(x) printf("%d\n",x)
- #define pfl(x) printf("%lld\n",x)
- #define flash ios_base::sync_with_stdio(false);cin.tie(0)
- #define goog(x) cout << "Case #" << x << ": "
- #define MAX5 100005
- #define MAX6 1000005
- #define MLOG 18
- #define limit 1e18
- #define mod 1000000007
- #define mod2 998244353
- typedef tree<
- int,
- null_type,
- less<int>,
- rb_tree_tag,
- tree_order_statistics_node_update>
- ordered_set;
- const ll Rval1DOM = chrono::high_resolution_clock::now().time_since_epoch().count();
- struct chash {
- ll operator()(pair<ll,ll> x) const { return (x.fi ^ Rval1DOM + x.se^Rval1DOM); }
- };
- #define ht gp_hash_table<pair<ll,ll>, ll, chash>
- ll power(ll x, ll y, ll p){
- ll res = 1;
- x = x % p;
- while (y > 0){
- if (y & 1)
- res = (res*x) % p;
- y = y>>1;
- x = (x*x) % p;
- }
- return res;
- }
- ht m;
- int arr[20003];
- ll p = 33179, p2 = 33179;
- int main(){
- int n;
- cin >> n;
- for(int i = 0; i < n; i++){
- cin >> arr[i];
- arr[i]++;
- }
- for(int i = 0; i < n; i++){
- arr[i+n] = arr[i];
- }
- int ind = 0;
- ll d = 33;
- ll h1 = 0, h2 = 0;
- string s;
- for(int i = 0; i < n; i++){
- h1 = 0;
- h2 = 0;
- s = "";
- for(int j = i; j < i+n; j++){
- d = ((arr[j])*power(p,j-i+1,mod))%mod;
- h1 = (h1 + d)%mod;
- d = ((arr[j])*power(p2,j-i+1,mod2))%mod2;
- h2 = (h2 + d)%mod2;
- s += (arr[j] + '0');
- m[{h1, h2}]++;
- }
- }
- reverse(arr, arr+2*n);
- for(ll i = 0; i < n; i++){
- h1 = 0;
- h2 = 0;
- for(ll j = i; j < i+n; j++){
- d = ((arr[j])*power(p,j-i+1,mod))%mod;
- h1 = (h1 + d)%mod;
- d = ((arr[j])*power(p2,j-i+1,mod2))%mod2;
- h2 = (h2 + d)%mod2;
- m[{h1, h2}]++;
- }
- }
- int cnt = 0;
- for(auto it = m.begin(); it != m.end(); it++){
- cnt++;
- }
- cout << cnt << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement