fork download
copy 
  1. // Problem Name: Distinct Substrings
  2. // Problem Link: https://c...content-available-to-author-only...s.fi/problemset/task/2105
  3.  
  4. #include <bits/stdc++.h>
  5. // #include <ext/pb_ds/assoc_container.hpp>
  6. // #include <ext/pb_ds/tree_policy.hpp>
  7.  
  8. using namespace std;
  9. // using namespace __gnu_pbds;
  10.  
  11. // #pragma GCCoptimize("O3")
  12. // #pragma GCCtarget("sse4")
  13. // #pragma GCCoptimize("unroll-loops")
  14.  
  15. #define vi vector<int>
  16. #define PB push_back
  17. #define vll vector<long long>
  18. #define ll long long
  19. #define all(x) x.begin(), x.end()
  20. #define F first
  21. #define S second
  22. #define ld long double
  23. #define vld vector<long double>
  24. #define pll pair<ll, ll>
  25. #define pii pair<int, int>
  26. #define vpii vector<pair<int, int>>
  27. #define GCD __gcd
  28.  
  29. const ll mod = 998244353;
  30. const ll MOD = 1e9 + 7;
  31. const ll INF = 1e18;
  32. const int inf = 1e9;
  33.  
  34. vector<int> sort_cyclic_shifts(string const &s){
  35.     int n = s.size();
  36.     const int alphabet = 256;
  37.     vi p(n), c(n), cnt(max(alphabet, n), 0);
  38.     for (int i = 0; i < n; i++){
  39.         cnt[s[i]]++;
  40.     }
  41.     for (int i = 1; i < alphabet; i++){
  42.         cnt[i] += cnt[i - 1];
  43.     }
  44.     for (int i = 0; i < n; i++){
  45.         p[--cnt[s[i]]] = i;
  46.     }
  47.     c[p[0]] = 0;
  48.     int classes = 1;
  49.     for (int i = 1; i < n; i++){
  50.         if (s[p[i]] != s[p[i - 1]]){
  51.             classes++;
  52.         }
  53.         c[p[i]] = classes - 1;
  54.     }
  55.     vi pn(n), cn(n);
  56.     for (int h = 0; (1 << h) < n; h++){
  57.         for (int i = 0; i < n; i++) {
  58.             pn[i] = p[i] - (1 << h);
  59.             if (pn[i] < 0) pn[i] += n;
  60.         }
  61.         fill(cnt.begin(), cnt.end(), 0);
  62.         for (int i = 0; i < n; i++){
  63.             cnt[c[pn[i]]]++;
  64.         }
  65.         for (int i = 1; i < classes; i++){
  66.             cnt[i] += cnt[i - 1];
  67.         }
  68.         for (int i = n - 1; i >= 0; i--){
  69.             p[--cnt[c[pn[i]]]] = pn[i];
  70.         }
  71.         cn[p[0]] = 0;
  72.         classes = 1;
  73.         for (int i = 1; i < n; i++){
  74.             pii cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
  75.             pii prev = {c[p[i - 1]], c[(p[i - 1] + (1 << h)) % n]};
  76.             if (cur != prev){
  77.                 classes++;
  78.             }
  79.             cn[p[i]] = classes - 1;
  80.         }
  81.         c.swap(cn);
  82.     }
  83.     return p;
  84. }
  85.  
  86. vector<int> suffix_array(string s){
  87.     s += '$';
  88.     vi ret = sort_cyclic_shifts(s);
  89.     ret = vi(ret.begin() + 1, ret.end());
  90.     return ret;
  91. }
  92.  
  93. vi buildLCP(string const &s, vi const &p){
  94.     int n = s.size();
  95.     vi rank(n, 0);
  96.     for (int i = 0; i < n; i++){
  97.         rank[p[i]] = i;
  98.     }
  99.  
  100.     int k = 0;
  101.     vi lcp(n, 0);
  102.     for (int i = 0; i < n; i++){
  103.         if (rank[i] == n - 1){
  104.             k = 0;
  105.             continue;
  106.         }
  107.         int j = p[rank[i] + 1];
  108.         while (i + k < n && j + k < n && s[i + k] == s[j + k]){
  109.             k++;
  110.         }
  111.         lcp[rank[i]] = k;
  112.         if (k) k--;
  113.     }
  114.     return lcp;
  115. }
  116.  
  117. void solve(int tst){
  118.     int n;
  119.     cin >> n;
  120.  
  121.     string s;
  122.     cin >> s;
  123.     vi p = suffix_array(s);
  124.     vi lcp = buildLCP(s, p);
  125.     lcp.PB(0);
  126.  
  127.     vll left(n), right(n);
  128.     stack<pll> st;
  129.     ll sum = 0;
  130.  
  131.     for (int i = 0; i < n; i++){
  132.         pll cur = {lcp[i], 1ll};
  133.         while (!st.empty() && st.top().F > cur.F){
  134.             pll top = st.top();
  135.             st.pop();
  136.             sum -= (top.F * top.S);
  137.             cur.S += top.S;
  138.         }
  139.         st.push(cur);
  140.         sum += (cur.F * cur.S);
  141.         left[i] = sum % mod;
  142.     }
  143.     while (!st.empty()) st.pop();
  144.     sum = 0;
  145.     for (int i = n - 1; i >= 0; i--){
  146.         pll cur = {lcp[i], 1ll};
  147.         while (!st.empty() && st.top().F > cur.F){
  148.             pll top = st.top();
  149.             st.pop();
  150.             sum -= (top.F * top.S);
  151.             cur.S += top.S;
  152.         }
  153.         st.push(cur);
  154.         sum += (cur.F * cur.S);
  155.         right[i] = sum % mod;
  156.     }
  157.  
  158.     ll ans = 0;
  159.     for (int i = 0; i + 1 < n; i++){
  160.         ans += (left[i] * right[i + 1]);
  161.         ans %= mod;
  162.     }
  163.     cout << ans << "\n";
  164. }
  165.  
  166. int main(){
  167.     ios_base::sync_with_stdio(0);
  168.     cin.tie(0);
  169.     // pre();
  170.     int tc = 1;
  171.     cin >> tc;
  172.     for (int i = 1; i <= tc; i++){
  173.         solve(i);
  174.     }
  175.     return 0;
  176. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
2
10
abababcxya
5
zzzax
stdout
copy 
19
2
https://ideone.com/UOtVDJ
language:
C++ 4.3.2 (gcc-4.3.2)
created:
23 hours 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!