Logo Infinity Online Judge

InfOJ

时间限制:1 s 空间限制:512 MB

#35. [NOIP2020] 字符串匹配

Statistics

题目描述

小 C 学习完了字符串匹配的相关内容,现在他正在做一道习题。

对于一个字符串 $S$,题目要求他找到 $S$ 的所有具有下列形式的拆分方案数: $S = ABC$,$S = ABABC$,$S = ABAB\cdots ABC$,其中 $A$,$B$,$C$ 均是非空字符串,且 $A$ 中出现奇数次的字符数量不超过 $C$ 中出现奇数次的字符数量。

更具体地,我们可以定义 $AB$ 表示两个字符串 $A, B$ 相连接,例如 $A = \text{aab}$,$B = \text{ab}$,则 $AB = \text{aabab}$。

并递归地定义 $A^1 = A$,$A^n = A^{n-1}A$($n\ge2$ 且为正整数)。例如 $A = \text{abb}$,则 $A^3 = \text{abbabbabb}$。

则小 C 的习题是求 $S = (AB)^iC$ 的方案数,其中 $F(A)\le F(C)$,$F(S )$ 表示字符串 $S$ 中出现奇数次的字符的数量。两种方案不同当且仅当拆分出的 $A$、$B$、$C$ 中有至少一个字符串不同。

小 C 并不会做这道题,只好向你求助,请你帮帮他。

输入格式

本题有多组数据,输入文件第一行一个正整数 $T$ 表示数据组数。

每组数据仅一行一个字符串 $S$,意义见题目描述。$S$ 仅由英文小写字母构成。

输出格式

对于每组数据输出一行一个整数表示答案。

样例

样例输入 1

3
nnrnnr
zzzaab
mmlmmlo

样例输出 1

8
9
16

样例解释

对于第一组数据,所有的方案为:

  1. $A=\color{blue}{\texttt{n}}$,$B=\color{blue}{\texttt{nr}}$,$C=\color{blue}{\texttt{nnr}}$。
  2. $A=\color{blue}{\texttt{n}}$,$B=\color{blue}{\texttt{nrn}}$,$C=\color{blue}{\texttt{nr}}$。
  3. $A=\color{blue}{\texttt{n}}$,$B=\color{blue}{\texttt{nrnn}}$,$C=\color{blue}{\texttt{r}}$。
  4. $A=\color{blue}{\texttt{nn}}$,$B=\color{blue}{\texttt{r}}$,$C=\color{blue}{\texttt{nnr}}$。
  5. $A=\color{blue}{\texttt{nn}}$,$B=\color{blue}{\texttt{rn}}$,$C=\color{blue}{\texttt{nr}}$。
  6. $A=\color{blue}{\texttt{nn}}$,$B=\color{blue}{\texttt{rnn}}$,$C=\color{blue}{\texttt{r}}$。
  7. $A=\color{blue}{\texttt{nnr}}$,$B=\color{blue}{\texttt{n}}$,$C=\color{blue}{\texttt{nr}}$。
  8. $A=\color{blue}{\texttt{nnr}}$,$B=\color{blue}{\texttt{nn}}$,$C=\color{blue}{\texttt{r}}$。

样例输入 2

5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab

样例输出 2

156
138
138
147
194

数据范围

测试点编号 $\vert S\vert \le $ 特殊限制
$1\sim 4$ $10$
$5\sim 8$ $100$
$9\sim 12$ $1000$
$13\sim 14$ $2^{15}$ $S$ 中只包含一种字符
$15\sim 17$ $2^{16}$ $S$ 中只包含两种字符
$18\sim 21$ $2^{17}$
$22\sim 25$ $2^{20}$

对于所有测试点,保证 $1\le T\le5$,$1\le |S|\le 2^{20}$。