1834: 【NOIP2020-T2】字符串匹配
[Creator : ]
Submit
Description
小C学习完了字符串匹配的相关内容，现在他正在做一道习题。
对于一个字符串S，题目要求他找到S的所有具有下列形式的拆分方案数：S=ABC，S=ABABC，S=ABAB···ABC，其中A，B，C均是非空字符串，且A中出现奇数次的字符数量不超过C中出现奇数次的字符数量。
更具体地，我们可以定义AB表示两个字符串A,B相连接，例如A=aab，B=ab，则AB=aabab。
并递归地定义A1=A，An=An−1A（n≥2且为正整数）。例如A=abb，则A3=abbabbabb。
则小C的习题是求S=(AB)iC的方案数，其中F(A)≤F(C)，F(S)表示字符串S中出现奇数次的字符的数量。两种方案不同当且仅当拆分出的A、B、C中有至少一个字符串不同。
小C并不会做这道题，只好向你求助，请你帮帮他。
对于一个字符串S，题目要求他找到S的所有具有下列形式的拆分方案数：S=ABC，S=ABABC，S=ABAB···ABC，其中A，B，C均是非空字符串，且A中出现奇数次的字符数量不超过C中出现奇数次的字符数量。
更具体地，我们可以定义AB表示两个字符串A,B相连接，例如A=aab，B=ab，则AB=aabab。
并递归地定义A1=A，An=An−1A（n≥2且为正整数）。例如A=abb，则A3=abbabbabb。
则小C的习题是求S=(AB)iC的方案数，其中F(A)≤F(C)，F(S)表示字符串S中出现奇数次的字符的数量。两种方案不同当且仅当拆分出的A、B、C中有至少一个字符串不同。
小C并不会做这道题，只好向你求助，请你帮帮他。
Input
本题有多组数据，输入文件第一行一个正整数T表示数据组数。
每组数据仅一行一个字符串S，意义见题目描述。S仅由英文小写字母构成。
每组数据仅一行一个字符串S，意义见题目描述。S仅由英文小写字母构成。
Output
对于每组数据输出一行一个整数表示答案。
Sample Input Copy
3
nnrnnr
zzzaab
mmlmmlo
Sample Output Copy
8
9
16
HINT
【样例1解释】
对于第一组数据，所有的方案为：
1.A=n，B=nr，C=nnr。
2.A=n，B=nrn，C=nr。
3.A=n，B=nrnn，C=r。
4.A=nn，B=r，C=nnr。
5.A=nn，B=rn，C=nr。
6.A=nn，B=rnn，C=r。
7.A=nnr，B=n，C=nr。
8.A=nnr，B=nn，C=r。
对于第一组数据，所有的方案为：
1.A=n，B=nr，C=nnr。
2.A=n，B=nrn，C=nr。
3.A=n，B=nrnn，C=r。
4.A=nn，B=r，C=nnr。
5.A=nn，B=rn，C=nr。
6.A=nn，B=rnn，C=r。
7.A=nnr，B=n，C=nr。
8.A=nnr，B=nn，C=r。