Summary

The deletion operation can be rephrased as “keep \(x\) characters from the beginning and \(M-x\) characters from the end”. We can efficiently count how many of the resulting strings are periodic using the Z-algorithm and the Möbius function.

Analysis

Let \(M\) be the length of the string after deletion. Since the deletion operation removes at least \(1\) character, \(0 \leq M \leq N-1\).

To form a string of length \(M\), we can think of it as:

• Keeping \(x\) characters from the beginning
• Keeping \(M-x\) characters from the end

That is, the string \(T\) after deletion is:

\[ T = S[0:x] + S[N-(M-x):N] \]

Here, \(0 \leq x \leq M\). This pair \((M, x)\) corresponds one-to-one with the choice of the deleted interval.

---

A periodic string is a string where, for some \(d < M\),

\[ T_i = T_{i+d} \]

holds for all \(0 \leq i < M-d\), and \(d\) divides \(M\). In this case, \(T\) is a string formed by repeating a block of length \(d\) for \(k = M/d\) times.

Simply trying all deletion operations would yield \(O(N^2)\) states, and performing periodicity checks on top of that would be too slow. Instead, for a fixed period length \(d\) and number of repetitions \(k\), we count the number of valid \(x\) values in bulk.

---

Let’s consider the condition for a string \(T\) of length \(M = dk\) to have a period length of \(d\).

The positions to compare are

\[ T_i = T_{i+d} \]

for the range \(0 \leq i < M-d\). Here, let

\[ C = M-d \]

The comparisons can be divided into the following three cases:

1. When both positions are in the part kept from the beginning

This requires the prefix of \(S\) to have a period of \(d\).

Using the Z-algorithm, if we find

\[ A[d] = d + \operatorname{LCP}(S[0:], S[d:]) \]

then the prefix of length up to \(A[d]\) will have a period of \(d\).

Thus, the necessary condition is:

\[ x \leq A[d] \]

2. When both positions are in the part kept from the end

Similarly, the suffix must have a period of \(d\).

This can be computed by applying the Z-algorithm to the reversed string. Supposing the suffix of length up to \(B[d]\) has a period of \(d\), we need:

\[ M-x \leq B[d] \]

which means:

\[ x \geq M - B[d] \]

Therefore, \(x\) must first lie in the following range:

\[ \max(0, M-B[d]) \leq x \leq \min(M, A[d]) \]

---

3. When the comparison spans across the “prefix part” and the “suffix part”

In this case, for the period \(d\) to hold, the corresponding characters in the prefix of length \(d\) and the suffix of length \(d\) must match.

That is, we need to check if

\[ S[t] = S[N-d+t] \]

for each \(0 \leq t < d\).

However, the required range of checks depends on the split position \(x\):

• If \(x\) is close to the left end: we only need to check a portion on the prefix side.
• If \(x\) is near the middle: the entire block of length \(d\) must match.
• If \(x\) is close to the right end: we only need to check a portion on the suffix side.

To handle this, we compute:

• firstBad[d]: the first mismatch position from the left between \(S[0:d]\) and \(S[N-d:N]\).
• lastBad[d]: the last mismatch position from the right.

If \(S[0:d] = S[N-d:N]\), the spanning comparison is always valid.

Otherwise, the spanning comparison holds if and only if:

\[ x \leq \text{firstBad}[d] \]

or

\[ x \geq C + \text{lastBad}[d] + 1 \]

Therefore, by finding the size of the intersection between these conditions and the candidate range for \(x\) obtained earlier, we can count the number of valid \(x\) for a fixed \((d, M)\).

---

Avoiding Double Counting

A string can have multiple period lengths.

For example, aaaa can be viewed as:

• a block of length \(1\) repeated \(4\) times,
• a block of length \(2\) repeated \(2\) times.

Therefore, simply counting by period length will result in double counting.

Here, we use the Möbius function \(\mu\).

Suppose a string of length \(M\) is formed by \(q\) repetitions of its minimal period. This string can also be viewed as a \(k\)-repetition string for any divisor \(k\) of \(q\).

Thus, we multiply the count for each repetition count \(k\) by the weight:

\[ -\mu(k) \]

and sum them up.

If the string is not periodic, then \(q=1\), so the contribution is \(0\). If the string is periodic, we have:

\[ \sum_{\substack{k \mid q \\ k \geq 2}} -\mu(k) = 1 \]

This allows us to count each periodic string exactly once.

Algorithm

1. Run the Z-algorithm on the string \(S\).
2. Run the Z-algorithm on the reversed string of \(S\).
3. Precompute the following for each \(d\):
   • A[d]: the maximum length from the beginning that has a period of \(d\).
   • B[d]: the maximum length from the end that has a period of \(d\).
   • firstBad[d]: the first mismatch position from the left between the first \(d\) characters and the last \(d\) characters.
   • lastBad[d]: the last mismatch position from the right between the first \(d\) characters and the last \(d\) characters.
4. Compute the Möbius function \(\mu\) using a linear sieve.
5. Iterate over the number of repetitions \(k \geq 2\):
   • The coefficient is coeff = -mu[k].
   • Iterate over \(d\) such that \(M = dk < N\).
   • For a fixed \(d\) and \(M\), find the number of deletion operations \(F\) that result in a string with period \(d\).
   • Add coeff * F to the answer.
6. Finally, handle the case where no deletion occurs (i.e., the original string \(S\) is kept).
   • If \(S\) itself is periodic, add \(1\) to the answer.
   • This can be checked by finding the minimal period using the prefix function (KMP pi array).

Complexity

• Time Complexity: \(O(N \log N)\)
• Space Complexity: \(O(N)\)

The double loop over \(k\) and \(d\) takes:

\[ \sum_{k=2}^{N} \frac{N}{k} = O(N \log N) \]

The precomputations for the Z-algorithm, prefix function, and Möbius function all take \(O(N)\) time.

Implementation Points

• It is easier to think of the deletion operation in terms of \((M, x)\):

  • \(M\): the length of the string after deletion.
  • \(x\): the number of characters kept from the beginning.

• Since the deletion operation requires \(M < N\), we only consider \(dk \leq N-1\) in the main loop.

• Keeping the entire string (no deletion) is a separate single case, so we check if \(S\) itself is periodic at the end.

• Empty strings and strings of length \(1\) are not periodic. Since the loop enforces \(k \geq 2\) and \(d \geq 1\), it naturally only considers lengths of at least \(2\).

  Source Code

#include <bits/stdc++.h>
using namespace std;

vector<int> z_function(const string& s) {
    int n = (int)s.size();
    vector<int> z(n);
    if (n == 0) return z;
    z[0] = n;
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i <= r) z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

vector<int> prefix_function(const string& s) {
    int n = (int)s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

vector<int> mobius(int n) {
    vector<int> mu(n + 1), primes;
    vector<bool> comp(n + 1);
    mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!comp[i]) {
            primes.push_back(i);
            mu[i] = -1;
        }
        for (int p : primes) {
            if ((long long)i * p > n) break;
            comp[i * p] = true;
            if (i % p == 0) {
                mu[i * p] = 0;
                break;
            } else {
                mu[i * p] = -mu[i];
            }
        }
    }
    return mu;
}

long long intersect_count(int l1, int r1, int l2, int r2) {
    int l = max(l1, l2);
    int r = min(r1, r2);
    if (l > r) return 0;
    return (long long)r - l + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    string S;
    cin >> N >> S;

    vector<int> z = z_function(S);
    string R = S;
    reverse(R.begin(), R.end());
    vector<int> zr = z_function(R);

    vector<int> A(N + 1), B(N + 1), firstBad(N + 1), lastBad(N + 1);

    for (int d = 1; d < N; d++) {
        A[d] = min(N, d + z[d]);
        B[d] = min(N, d + zr[d]);

        int fb = z[N - d];
        if (fb > d) fb = d;
        firstBad[d] = fb;

        int eb = zr[N - d];
        if (eb > d) eb = d;
        if (eb >= d) lastBad[d] = -1;
        else lastBad[d] = d - 1 - eb;
    }

    vector<int> mu = mobius(N);

    long long ans = 0;

    for (int k = 2; k <= N - 1; k++) {
        int coeff = -mu[k];
        if (coeff == 0) continue;

        int maxd = (N - 1) / k;
        for (int d = 1; d <= maxd; d++) {
            int M = d * k;
            int C = M - d;

            int lo = max(0, M - B[d]);
            int hi = min(M, A[d]);
            if (lo > hi) continue;

            long long F = 0;
            if (firstBad[d] == d) {
                F = (long long)hi - lo + 1;
            } else {
                F += intersect_count(lo, hi, 0, firstBad[d]);
                F += intersect_count(lo, hi, C + lastBad[d] + 1, M);
            }

            ans += (long long)coeff * F;
        }
    }

    if (N >= 2) {
        vector<int> pi = prefix_function(S);
        int p = N - pi[N - 1];
        if (p < N && N % p == 0) ans++;
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.