题目描述
小 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 并不会做这道题,只好向你求助,请你帮帮他。
输入格式
从文件 string.in
中读入数据。
本题有多组数据,输入文件第一行一个正整数 T 表示数据组数。
每组数据仅一行一个字符串 S,意义见题目描述。S 仅由英文小写字母构成。
输出格式
输出到文件 string.out
中。
对于每组数据输出一行一个整数表示答案。
样例 1
3
nnrnnr
zzzaab
mmlmmlo
8
9
16
对于第一组数据,所有的方案为:
- A=n,B=nr,C=nnr。
- A=n,B=nrn,C=nr。
- A=n,B=nrnn,C=r。
- A=nn,B=r,C=nnr。
- A=nn,B=rn,C=nr。
- A=nn,B=rnn,C=r。
- A=nnr,B=n,C=nr。
- A=nnr,B=nn,C=r。
5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab
156
138
138
147
194
样例 3
见附加文件中的 [string3.in
](file:string3.in) 与 [string3.ans
](file:string3.ans)。
样例 4
见附加文件中的 [string4.in
](file:string4.in) 与 [string4.ans
](file:string4.ans)。
数据范围与提示
测试点编号 |
∣S∣≤ |
特殊限制 |
1∼4 |
10 |
无 |
5∼8 |
100 |
9∼12 |
1000 |
13∼14 |
215 |
S 中只包含一种字符 |
15∼17 |
216 |
S 中只包含两种字符 |
18∼21 |
217 |
无 |
22∼25 |
220 |
对于所有测试点,保证 1≤T≤5,1≤∣S∣≤220。