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