310086: CF1780G. Delicious Dessert
Memory Limit：512 MB
Time Limit：3 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Delicious Dessert
题意翻译
有一个字符串 $s$。 求 $s$ 中子串出现次数恰好是其长度倍数时的这些子串的总数量。 Translated by [Tx_Lcy](https://www.luogu.com.cn/user/253608)题目描述
Today is an important day for chef Tonio — an auditor has arrived in his hometown of Morioh. He has also arrived at Tonio's restaurant and ordered dessert. Tonio has not been prepared for this turn of events. As you know, dessert is a string of lowercase English letters. Tonio remembered the rule of desserts — a string $ s $ of length $ n $ . Any dessert $ t $ is delicious if the number of occurrences of $ t $ in $ s $ as a substring is divisible by the length of $ t $ . Now Tonio wants to know the number of delicious substrings of $ s $ . If the substring occurs several times in the string $ s $ , then all occurrences must be taken into account.输入输出格式
输入格式
The first line contains an integer $ n $ ( $ 1 \leq n \leq 10^6 $ ) — the length of the rule $ s $ . The second line contains the string $ s $ of length $ n $ — the rule. The rule consists only of lowercase English letters.
输出格式
In a single line print the number of delicious substrings of $ s $ .
输入输出样例
输入样例 #1
7
abacaba输出样例 #1
11输入样例 #2
8
abaababa输出样例 #2
11输入样例 #3
10
deadinside输出样例 #3
12输入样例 #4
5
aaaaa输出样例 #4
12说明
In the first sample, there are many delicious substrings. $ 7 $ of them are substrings of length $ 1 $ (because any number is divisible by $ 1 $ ). Consider other delicious substrings: - "ab" occurs in $ s $ $ 2 $ times, which is divisible by the length of the substring. - "ba" also occurs $ 2 $ times. Therefore, the answer is $ 7 + 2 + 2 = 11 $ . Note that the answer includes both occurrences of "ab" and "ba".Input
题意翻译
有一个字符串 $s$。 求 $s$ 中子串出现次数恰好是其长度倍数时的这些子串的总数量。 Translated by [Tx_Lcy](https://www.luogu.com.cn/user/253608)Output
**题目大意**：
给定一个字符串 \( s \)。需要找出所有在 \( s \) 中出现的子串，使得子串出现的次数恰好是其长度的倍数。计算这些子串的总数量。
**输入输出数据格式**：
- **输入格式**：
- 第一行包含一个整数 \( n \) \( (1 \leq n \leq 10^6) \)，表示字符串 \( s \) 的长度。
- 第二行包含一个长度为 \( n \) 的字符串 \( s \)，字符串仅由小写英文字母组成。
- **输出格式**：
- 输出包含一个整数，表示 \( s \) 中满足条件的子串的总数量。
**输入输出样例**：
- **输入样例 #1**：
- 7
- abacaba
- **输出样例 #1**：
- 11
- **输入样例 #2**：
- 8
- abaababa
- **输出样例 #2**：
- 11
- **输入样例 #3**：
- 10
- deadinside
- **输出样例 #3**：
- 12
- **输入样例 #4**：
- 5
- aaaaa
- **输出样例 #4**：
- 12**题目大意**： 给定一个字符串 \( s \)。需要找出所有在 \( s \) 中出现的子串，使得子串出现的次数恰好是其长度的倍数。计算这些子串的总数量。 **输入输出数据格式**： - **输入格式**： - 第一行包含一个整数 \( n \) \( (1 \leq n \leq 10^6) \)，表示字符串 \( s \) 的长度。 - 第二行包含一个长度为 \( n \) 的字符串 \( s \)，字符串仅由小写英文字母组成。 - **输出格式**： - 输出包含一个整数，表示 \( s \) 中满足条件的子串的总数量。 **输入输出样例**： - **输入样例 #1**： - 7 - abacaba - **输出样例 #1**： - 11 - **输入样例 #2**： - 8 - abaababa - **输出样例 #2**： - 11 - **输入样例 #3**： - 10 - deadinside - **输出样例 #3**： - 12 - **输入样例 #4**： - 5 - aaaaa - **输出样例 #4**： - 12
给定一个字符串 \( s \)。需要找出所有在 \( s \) 中出现的子串，使得子串出现的次数恰好是其长度的倍数。计算这些子串的总数量。
**输入输出数据格式**：
- **输入格式**：
- 第一行包含一个整数 \( n \) \( (1 \leq n \leq 10^6) \)，表示字符串 \( s \) 的长度。
- 第二行包含一个长度为 \( n \) 的字符串 \( s \)，字符串仅由小写英文字母组成。
- **输出格式**：
- 输出包含一个整数，表示 \( s \) 中满足条件的子串的总数量。
**输入输出样例**：
- **输入样例 #1**：
- 7
- abacaba
- **输出样例 #1**：
- 11
- **输入样例 #2**：
- 8
- abaababa
- **输出样例 #2**：
- 11
- **输入样例 #3**：
- 10
- deadinside
- **输出样例 #3**：
- 12
- **输入样例 #4**：
- 5
- aaaaa
- **输出样例 #4**：
- 12**题目大意**： 给定一个字符串 \( s \)。需要找出所有在 \( s \) 中出现的子串，使得子串出现的次数恰好是其长度的倍数。计算这些子串的总数量。 **输入输出数据格式**： - **输入格式**： - 第一行包含一个整数 \( n \) \( (1 \leq n \leq 10^6) \)，表示字符串 \( s \) 的长度。 - 第二行包含一个长度为 \( n \) 的字符串 \( s \)，字符串仅由小写英文字母组成。 - **输出格式**： - 输出包含一个整数，表示 \( s \) 中满足条件的子串的总数量。 **输入输出样例**： - **输入样例 #1**： - 7 - abacaba - **输出样例 #1**： - 11 - **输入样例 #2**： - 8 - abaababa - **输出样例 #2**： - 11 - **输入样例 #3**： - 10 - deadinside - **输出样例 #3**： - 12 - **输入样例 #4**： - 5 - aaaaa - **输出样例 #4**： - 12