Overview

We count the number of operations that result in a string \(T\) which is a repetition of the same string \(2\) or more times, considering both the case where no deletion is performed and the case where exactly one contiguous substring is deleted.

We represent the string after deletion by the “length kept from the beginning” and the “length kept from the end”, and count them quickly using the Z-algorithm and Möbius inversion.

Analysis

We rephrase the deletion operation as follows.

Let \(L\) be the length of the string after deletion, and \(a\) be the number of characters kept from the beginning.

Then, the number of characters kept from the end is \(L-a\), and the resulting string is

\[ T = S[0:a] + S[N-(L-a):N] \]

When performing a deletion, we have \(0 \leq L < N\) and \(0 \leq a \leq L\).
For a fixed \(L\), the choice of \(a\) uniquely corresponds (one-to-one) to the choice of the deleted interval.

---

Directly Checking Periodicity is Too Slow

There are

\[ \frac{N(N+1)}{2} \]

ways of choosing the deletion operation.

If we construct \(T\) and check its periodicity for each operation, it would take nearly \(O(N^3)\) in the worst case, which is far too slow for \(N \leq 5 \times 10^5\).

---

Counting “Is Periodic” using Möbius Inversion

A string \(T\) of length \(L\) is periodic if there exists some \(Q \geq 2\) such that it has a period of length

\[ p = \frac{L}{Q} \]

In other words, \(T\) is a repetition of a block of length \(p\) exactly \(Q\) times.

However, the same string can have multiple periods.
For example, aaaa has period lengths of both \(1\) and \(2\).

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

For a string \(T\) of length \(L\), the indicator function for \(T\) being periodic can be expressed as follows:

\[ \sum_{\substack{Q \mid L \\ Q \geq 2 \\ T \text{ has period } L/Q}} -\mu(Q) \]

This is based on the following properties:

• Let \(d\) be the minimum period length of \(T\).
• Letting \(K = L/d\), \(T\) is a repetition of the same string \(K\) times.
• \(T\) has period \(L/Q\) if and only if \(Q \mid K\).
• Thus, the contribution is

\[ \sum_{\substack{Q \mid K \\ Q \geq 2}} -\mu(Q) \]

If \(K=1\) (i.e., \(T\) is not periodic), the sum is \(0\).
If \(K \geq 2\), it is:

\[ -\left(\sum_{Q \mid K}\mu(Q)-1\right)=1 \]

Therefore, for each \(Q\) and \(p\), we can count the number of deleted strings with length \(L = pQ\) that have period \(p\), and sum them up after multiplying by \(-\mu(Q)\).

---

Counting for a Fixed Period Length \(p\) and Length \(L=pQ\)

Let the string after deletion be

\[ T = S[0:a] + S[N-(L-a):N] \]

Now, let us consider the conditions for \(T\) to have period \(p\).

Since \(T\) is a concatenation of the prefix part and the suffix part, the periodic conditions can be broadly classified into the following three types:

1. Period \(p\) holds internally within the prefix part \(S[0:a]\).
2. Period \(p\) holds internally within the suffix part \(S[N-(L-a):N]\).
3. Period \(p\) holds across the boundary between the prefix part and the suffix part.

---

1. Condition for the Prefix Part

For \(S[0:a]\) to have period \(p\), we need

\[ S[i] = S[i+p] \]

to hold for all \(0 \leq i < a-p\).

Using the Z-algorithm, let \(z[p]\) be the length of the longest common prefix of \(S\) and \(S[p:]\). Then, the condition is:

\[ a-p \leq z[p] \]

That is,

\[ a \leq p + z[p] \]

---

2. Condition for the Suffix Part

The suffix part is taken from the end of \(S\).

By using the Z-algorithm on the reversed string, we can find how far the relation

\[ S[i] = S[i+p] \]

holds continuously from the end.

Let this value be rz[p].

Since the length of the suffix part is \(L-a\), the condition to have period \(p\) is:

\[ L-a-p \leq rz[p] \]

Rewriting this, we get:

\[ a \geq L-p-rz[p] \]

---

3. Condition for the Boundary

So far, we know that the prefix and suffix parts internally have period \(p\).

Additionally, the characters at the same position modulo \(p\) in the prefix part and the suffix part must match.

The reference string of length \(p\) for the prefix part is

\[ S[0:p] \]

Since the suffix part is aligned to the end, the reference string of length \(p\) for the suffix part is

\[ S[N-p:N] \]

We compare these two.

• Let \(x\) be the number of matching characters from the beginning.
• Let \(y\) be the number of matching characters from the end.

These can be obtained as follows:

x = z[N-p]
y = rz[N-p]

If \(x \geq p\), then \(S[0:p]\) and \(S[N-p:N]\) match completely, so the boundary condition is always satisfied.

Otherwise, \(a\) satisfies the boundary condition if and only if one of the following holds:

• The boundary is to the left, and the required matching part is only on the prefix side:
  $\(a \leq x\)$
• The boundary is to the right, and the required matching part is only on the suffix side:
  $\(a \geq L-y\)$

---

Putting It Together

For fixed \(p\) and \(L\), we first find the range of \(a\) from the internal conditions of the prefix and suffix parts.

\[ lo = \max(0, L-p-rz[p]) \]

\[ hi = \min(L, p+z[p]) \]

Any \(a\) within this range \([lo, hi]\) is a candidate.

Next, we consider the boundary conditions.

• If \(S[0:p] = S[N-p:N]\), all candidates are valid.
• Otherwise, among the candidates, we only count those that satisfy:
  • \(a \leq x\)
  • or \(a \geq L-y\)

Letting \(C(p,L)\) be this count, the contribution of the deletion operations to the answer is:

\[ -\mu(Q) \times C(p,L) \]

---

Case with No Deletion

We handle the case of no deletion (i.e., \(T=S\)) separately.

We just need to check if \(S\) is a periodic string.

If a string of length \(N\) is periodic, it has a period length of

\[ p = \frac{N}{q} \]

for some prime \(q \mid N\).

Therefore, if there exists a prime factor \(q\) of \(N\) such that

\[ z[p] \geq N-p \]

then \(S\) is periodic.

In this case, we add \(1\) to the answer.

Algorithm

1. Run the Z-algorithm on \(S\) to obtain the array z.
2. Run the Z-algorithm on the reversed string \(S[::-1]\) to obtain the array rz.
3. Compute the Möbius function \(\mu\) and the list of prime numbers using a linear sieve.
4. Check the case with no deletion, and add \(1\) to the answer if \(S\) is periodic.
5. For each \(Q \geq 2\), process only if \(\mu(Q) \neq 0\).
6. For each \(p\), let \(L=pQ<N\), and count the number of deletion operations that result in a string with period \(p\).
7. Multiply this count by \(-\mu(Q)\) and add it to the answer.

Complexity

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

The computations of the Z-algorithm and the Möbius function both take \(O(N)\) time.

The subsequent nested loops take

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

time.

Implementation Notes

• z[i] in the Z-algorithm is the length of the longest common prefix of \(S\) and \(S[i:]\).

• By using the Z-algorithm on the reversed string, we can quickly compute matching lengths from the end.

• A deletion operation can be uniquely represented by the length after deletion \(L\) and the length kept from the beginning \(a\).

• Although empty strings or strings of length \(1\) are not periodic, they are naturally excluded because we count with \(L = pQ\), \(Q \geq 2\), and \(p \geq 1\).

• The answer fits within a 64-bit integer, but in Python, there is no need to worry about integer overflow.

  Source Code

import sys


def z_algorithm(s):
    n = len(s)
    z = [0] * n
    z[0] = n
    l = r = 0
    for i in range(1, n):
        if i < r:
            v = z[i - l]
            rem = r - i
            if v > rem:
                v = rem
        else:
            v = 0
        while i + v < n and s[v] == s[i + v]:
            v += 1
        z[i] = v
        if i + v > r:
            l = i
            r = i + v
    return z


def mobius_and_primes(n):
    mu = [0] * (n + 1)
    mu[1] = 1
    primes = []
    comp = bytearray(n + 1)
    for i in range(2, n + 1):
        if not comp[i]:
            primes.append(i)
            mu[i] = -1
        for p in primes:
            v = i * p
            if v > n:
                break
            comp[v] = 1
            if i % p == 0:
                mu[v] = 0
                break
            mu[v] = -mu[i]
    return mu, primes


def main():
    input = sys.stdin.buffer.readline
    N = int(input())
    S = input().strip()

    z = z_algorithm(S)
    rz = z_algorithm(S[::-1])

    mu, primes = mobius_and_primes(N)

    ans = 0

    if N >= 2:
        tmp = N
        ok = False
        for q in primes:
            if q * q > tmp:
                break
            if tmp % q == 0:
                p = N // q
                if z[p] >= N - p:
                    ok = True
                    break
                while tmp % q == 0:
                    tmp //= q
        if not ok and tmp > 1:
            q = tmp
            p = N // q
            if z[p] >= N - p:
                ok = True
        if ok:
            ans = 1

    NN = N
    zloc = z
    rzloc = rz
    muloc = mu

    for Q in range(2, NN):
        m = muloc[Q]
        if m == 0:
            continue
        sign = -m
        maxp = (NN - 1) // Q
        L = Q
        for p in range(1, maxp + 1):
            pre = p + zloc[p]
            hi = pre if pre < L else L

            lo = L - p - rzloc[p]
            if lo < 0:
                lo = 0

            if lo <= hi:
                idx = NN - p
                x = zloc[idx]

                if x >= p:
                    cnt = hi - lo + 1
                else:
                    cnt = 0

                    if lo <= x:
                        e = hi if hi < x else x
                        cnt += e - lo + 1

                    y = rzloc[idx]
                    st = L - y
                    if hi >= st:
                        s = lo if lo > st else st
                        cnt += hi - s + 1

                ans += sign * cnt

            L += Q

    print(ans)


if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.