题目描述

小 C 学习完了字符串匹配的相关内容，现在他正在做一道习题。
对于一个字符串 S，题目要求他找到 S 的所有具有下列形式的拆分方案数: S=ABC,S=ABABC,S=ABAB⋯ABC，其中 A,B,C 均是非空字符串，且 A 中出现奇数次的字符数量不超过 C 中出现奇数次的字符数量。
更具体地，我们可以定义 AB 表示两个字符串 A,B 相连接，例如 A=aab,B=ab，则 AB=aabab。
并递归地定义 A¹=A,Aⁿ=Aⁿ⁻¹A（n≥2 且为正整数）。例如 A=abb，则 A³=abbabbabb。
则小 C 的习题是求 S=(AB)ⁱC 的方案数，其中 F(A)≤F(C)，F(S) 表示字符串 S 中出现奇数次的字符的数量。两种方案不同当且仅当拆分出的 A、B、C 中有至少一个字符串不同。
小 C 并不会做这道题，只好向你求助，请你帮帮他。

输入

本题有多组数据，输入的第一行一个正整数 T 表示数据组数。
每组数据仅一行一个字符串 S，意义见题目描述。S 仅由英文小写字母构成。

输出

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

样例输入 Copy

3
nnrnnr
zzzaab
mmlmmlo

样例输出 Copy

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。
样例二
input
15
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab

output
156
138
138
147
194
限制与约定

测试点编号	\|S\|≤	特殊性质
1∼4	10
5∼8	100
9∼12	1000
13∼14	2¹⁵	S 中只包含一种字符
15∼17	2¹⁶	S 中只包含两种字符
18∼21	2¹⁷
22∼25	2²⁰

对于所有测试点，保证 1≤T≤5，1≤|S|≤2²⁰。

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

来源/分类

NOIP提高组 NOIP2020 exKMP

1921: 【NOIP2020提高组】字符串匹配

题目描述

输入

输出

样例输入 Copy

样例输出 Copy

提示

来源/分类