fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. // حساب GCD
  6. ll gcdll(ll a, ll b) {
  7.     return b==0 ? a : gcdll(b, a%b);
  8. }
  9.  
  10. int main(){
  11.     ios::sync_with_stdio(false);
  12.     cin.tie(nullptr);
  13.  
  14.     int N; 
  15.     cin >> N;
  16.     vector<int> V(N);
  17.     for(int &x: V) cin >> x;
  18.  
  19.     // 1) ضغط القيم إلى [0..N-1]
  20.     {
  21.         auto W = V;
  22.         sort(W.begin(), W.end());
  23.         W.erase(unique(W.begin(), W.end()), W.end());
  24.         for(int &x: V) x = int(lower_bound(W.begin(), W.end(), x) - W.begin());
  25.     }
  26.  
  27.     // 2) بناء الـ Suffix Array
  28.     vector<int> sa(N), rnk(N), tmp(N);
  29.     for(int i=0;i<N;i++){
  30.         sa[i]=i;
  31.         rnk[i]=V[i];
  32.     }
  33.     for(int k=1;;k<<=1){
  34.         auto cmp = [&](int a,int b){
  35.             if(rnk[a]!=rnk[b]) return rnk[a]<rnk[b];
  36.             int ra = a+k<N ? rnk[a+k] : -1;
  37.             int rb = b+k<N ? rnk[b+k] : -1;
  38.             return ra<rb;
  39.         };
  40.         sort(sa.begin(), sa.end(), cmp);
  41.         tmp[sa[0]] = 0;
  42.         for(int i=1;i<N;i++){
  43.             tmp[sa[i]] = tmp[sa[i-1]] + cmp(sa[i-1], sa[i]);
  44.         }
  45.         rnk = tmp;
  46.         if(rnk[sa[N-1]]==N-1) break;
  47.     }
  48.  
  49.     // 3) حساب LCP (Kasai)
  50.     vector<int> inv(N), lcp(N);
  51.     for(int i=0;i<N;i++) inv[sa[i]] = i;
  52.     int h = 0;
  53.     for(int i=0;i<N;i++){
  54.         if(inv[i]>0){
  55.             int j = sa[inv[i]-1];
  56.             while(i+h<N && j+h<N && V[i+h]==V[j+h]) h++;
  57.             lcp[inv[i]] = h;
  58.             if(h>0) h--;
  59.         }
  60.     }
  61.  
  62.     // 4) مجموع LCP(i,j) لجميع i<j عبر subarray-minimums
  63.     int M = N-1;
  64.     vector<ll> A(M+1);
  65.     for(int k=1;k<=M;k++){
  66.         A[k] = lcp[k];
  67.     }
  68.  
  69.     vector<ll> ple(M+1), nle(M+1);
  70.     stack<int> st;
  71.     // PLE
  72.     for(int i=1;i<=M;i++){
  73.         while(!st.empty() && A[st.top()] >= A[i]) st.pop();
  74.         ple[i] = st.empty() ? 0 : st.top();
  75.         st.push(i);
  76.     }
  77.     while(!st.empty()) st.pop();
  78.     // NLE
  79.     for(int i=M;i>=1;i--){
  80.         while(!st.empty() && A[st.top()] > A[i]) st.pop();
  81.         nle[i] = st.empty() ? (M+1) : st.top();
  82.         st.push(i);
  83.     }
  84.  
  85.     ll sumPairs = 0;
  86.     for(int k=1;k<=M;k++){
  87.         ll leftCnt  = k - ple[k];
  88.         ll rightCnt = nle[k] - k;
  89.         sumPairs += A[k] * leftCnt * rightCnt;
  90.     }
  91.  
  92.     // 5) أضف مطابقات النفس
  93.     ll sumSelf = (ll)N*(N+1)/2;
  94.     ll total   = sumSelf + 2*sumPairs;
  95.     ll denom   = (ll)N * N;
  96.     ll g       = gcdll(total, denom);
  97.  
  98.     cout << (total/g) << "/" << (denom/g) << "\n";
  99.     return 0;
  100. }
Success #stdin #stdout 0s 5332KB
comments (?)
stdin
copy 
4
1 1 1 1
stdout
copy 
15/8
https://ideone.com/XpZUWX
language:
C++ (gcc 8.3)
created:
8 days 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!