/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 533 点
問題文
高橋君は長さ N の文字列 S を持っています。S は英小文字からなります。
高橋君は文字列 S に対して、次の2種類の操作のうちちょうど1つを選んで行い、文字列 T を得ます。
- 操作1（削除しない）： T = S とする。
- 操作2（連続する区間を削除する）： 1 \leq l \leq r \leq N を満たす整数の組 (l, r) を1つ選び、S の l 文字目から r 文字目までを削除する。すなわち、S の 1 文字目から l-1 文字目までと、r+1 文字目から N 文字目までをこの順に連結したものを T とする。l = 1 のとき前半部分は空、r = N のとき後半部分は空とする。l \leq r より少なくとも 1 文字は削除されるため、T の長さは N より真に短くなります。特に l = 1 かつ r = N のとき T は空文字列となります。
高橋君の目標は、得られた文字列 T が周期文字列となるようにすることです。
ここで、文字列 T が周期文字列であるとは、ある長さ 1 以上の文字列 P と整数 k \geq 2 が存在して、T が P をちょうど k 回繰り返した文字列に一致することを指します。すなわち、|T| = k \cdot |P| かつ T = \underbrace{PP\cdots P}_{k} が成り立つことです。このような P と k の組が1つでも存在すれば周期文字列です（P が最小の繰り返し単位である必要はありません）。この定義より、空文字列および長さ 1 の文字列は周期文字列ではないことに注意してください。
操作の選び方の総数は、操作1の 1 通りと、操作2における (l, r) の選び方 \frac{N(N+1)}{2} 通りを合わせた 1 + \frac{N(N+1)}{2} 通りです。このうち、得られる文字列 T が周期文字列となるような操作の選び方の数を求めてください。
なお、異なる操作の選び方から結果として同じ文字列 T が得られる場合でも、それぞれ別々に数えます。
制約
- 1 \leq N \leq 5 \times 10^5
- S は英小文字からなる長さ N の文字列
- 答えは 64 bit 符号付き整数型に収まる
入力
N S
- 1 行目には、文字列の長さを表す整数 N が与えられる。
- 2 行目には、英小文字からなる長さ N の文字列 S が与えられる。
出力
得られる文字列 T が周期文字列となるような操作の選び方の数を1行で出力せよ。
入力例 1
4 abab
出力例 1
1
入力例 2
3 abc
出力例 2
0
入力例 3
30 abcabcabcabcabcabcabcabcabcabc
出力例 3
141
入力例 4
120 abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnop
出力例 4
8
入力例 5
1 a
出力例 5
0
Score : 533 pts
Problem Statement
Takahashi has a string S of length N. S consists of lowercase English letters.
Takahashi chooses and performs exactly one of the following two types of operations on the string S to obtain a string T.
- Operation 1 (Do not delete): Let T = S.
- Operation 2 (Delete a contiguous interval): Choose a pair of integers (l, r) satisfying 1 \leq l \leq r \leq N, and delete the characters from the l-th character to the r-th character of S. That is, let T be the concatenation of the 1-st to (l-1)-th characters of S and the (r+1)-th to N-th characters of S in this order. If l = 1, the first part is empty; if r = N, the second part is empty. Since l \leq r, at least one character is deleted, so the length of T is strictly shorter than N. In particular, when l = 1 and r = N, T becomes an empty string.
Takahashi's goal is to make the resulting string T a periodic string.
Here, a string T is called a periodic string if there exists a string P of length at least 1 and an integer k \geq 2 such that T is equal to the string obtained by repeating P exactly k times. That is, |T| = k \cdot |P| and T = \underbrace{PP\cdots P}_{k} hold. If there is at least one such pair of P and k, then T is a periodic string (it is not necessary for P to be the minimal repeating unit). Note that by this definition, an empty string and a string of length 1 are not periodic strings.
The total number of ways to choose an operation is 1 + \frac{N(N+1)}{2}, which consists of 1 way for Operation 1 and \frac{N(N+1)}{2} ways to choose (l, r) in Operation 2. Among these, find the number of choices of operations such that the resulting string T is a periodic string.
Note that even if different choices of operations result in the same string T, they are counted separately.
Constraints
- 1 \leq N \leq 5 \times 10^5
- S is a string of length N consisting of lowercase English letters.
- The answer fits within a 64-bit signed integer.
Input
N S
- The first line contains an integer N, representing the length of the string.
- The second line contains a string S of length N consisting of lowercase English letters.
Output
Print the number of choices of operations such that the resulting string T is a periodic string in a single line.
Sample Input 1
4 abab
Sample Output 1
1
Sample Input 2
3 abc
Sample Output 2
0
Sample Input 3
30 abcabcabcabcabcabcabcabcabcabc
Sample Output 3
141
Sample Input 4
120 abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnop
Sample Output 4
8
Sample Input 5
1 a
Sample Output 5
0