P6273 [eJOI 2017] 魔法
题目描述
给定一个长度为 $n$ 的字符串 $S$。设 $S$ 中不同的字符数为 $k$ 。
定义字符串的子串为该字符串某一连续段。
而 ***有魔法的子串*** 被定义为 $S$ **的某一非空子串,满足该子串中不同的字符数为** $k$ **,且每个字符的出现的次数都相同**。
你需要求出给定字符串 $S$ 的不同的 有魔法的子串 的个数。
若两个子串的左右端点不同,则这两个子串不同。
输入格式
无
输出格式
无
说明/提示
#### 【输入输出样例解释】
**样例 1 解释**
- 满足条件的子串有: $\texttt{abc},\texttt{cba},\texttt{abc},\texttt{abccba}$
**样例 2 解释**
- 仅子串 $\texttt{abcABC}$ 为 有魔法的子串(区分大小写,即 $\texttt{a}\ne \texttt{A}$)。
**样例 3 解释**
- 其中一个是 $\texttt{SwSwwS}$。
#### 【数据规模与约定】
**本题采用多测试点捆绑测试,共有 4 个子任务**。
- Subtask 1(10 points):$2\le n\le 100$。
- Subtask 2(20 points):$2\le n\le 2\times 10^3$。
- Subtask 3(30 points):$2\le n\le 10^5,k=2$ (即 $S$ 中只有两种字符)。
- Subtask 4(40 points):无其他限制。
对于所有数据,保证 $2\le n\le 10^5$,字符集为 $ [\texttt{a},\texttt{z}] \cup [\texttt{A},\texttt{Z}]$
#### 【说明】
原题来自:[eJOI 2017](www.ejoi.org) Problem A [Magic](http://ejoi.org/wp-content/themes/ejoi/assets/pdfs/tasks_day_1/EN/magic_statement-en.pdf)
翻译提供:@[```_Wallace_```](https://www.luogu.com.cn/user/61430)