#P7114. [NOIP2020] 字符串匹配

[NOIP2020] 字符串匹配

题目描述

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

对于一个字符串 SS,题目要求他找到 SS 的所有具有下列形式的拆分方案数:

S=ABCS = ABCS=ABABCS = ABABCS=ABABABCS = ABAB \ldots ABC,其中 AABBCC 均是非空字符串,且 AA 中出现奇数次的字符数量不超过 CC 中出现奇数次的字符数量。

更具体地,我们可以定义 ABAB 表示两个字符串 AABB 相连接,例如 A=aabA = \texttt{aab}B=abB = \texttt{ab},则 AB=aababAB = \texttt{aabab}

并递归地定义 A1=AA^1=AAn=An1AA^n = A^{n - 1} An2n \ge 2 且为正整数)。例如 A=abbA = \texttt{abb},则 A3=abbabbabbA^3=\texttt{abbabbabb}

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

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

输入格式

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

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

输出格式

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

3
nnrnnr
zzzaab
mmlmmlo

8
9
16

5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab

156
138
138
147
194

见附件中的 string/string3.in
见附件中的 string/string3.ans
见附件中的 string/string4.in
见附件中的 string/string4.ans

提示

【样例 #1 解释】

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

  1. A=nA=\texttt{n}B=nrB=\texttt{nr}C=nnrC=\texttt{nnr}
  2. A=nA=\texttt{n}B=nrnB=\texttt{nrn}C=nrC=\texttt{nr}
  3. A=nA=\texttt{n}B=nrnnB=\texttt{nrnn}C=rC=\texttt{r}
  4. A=nnA=\texttt{nn}B=rB=\texttt{r}C=nnrC=\texttt{nnr}
  5. A=nnA=\texttt{nn}B=rnB=\texttt{rn}C=nrC=\texttt{nr}
  6. A=nnA=\texttt{nn}B=rnnB=\texttt{rnn}C=rC=\texttt{r}
  7. A=nnrA=\texttt{nnr}B=nB=\texttt{n}C=nrC=\texttt{nr}
  8. A=nnrA=\texttt{nnr}B=nnB=\texttt{nn}C=rC=\texttt{r}

【数据范围】

测试点编号 S\lvert S \rvert \le 特殊性质
141 \sim 4 1010
585 \sim 8 100100
9129 \sim 12 10001000
131413 \sim 14 2152^{15} SS 中只包含一种字符
151715 \sim 17 2162^{16} SS 中只包含两种字符
182118 \sim 21 2172^{17}
222522 \sim 25 2202^{20}

对于所有测试点,保证 1T51 \le T \le 51S2201 \le |S| \le 2^{20}