【NOIP2020】字符串匹配 - 题目

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

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

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

并递归地定义 $A^{1} = A, A^{n} = A^{n - 1} A$ （ $n \geq 2$ 且为正整数）。例如 $A = abb$ ，则 $A^{3} = abbabbabb$ 。

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

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

输入格式

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

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

输出格式

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

样例一

input

3
nnrnnr
zzzaab
mmlmmlo

output

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

5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab

output

样例三

见附加文件中的 ex_string3.in/ans。

样例四

见附加文件中的 ex_string4.in/ans。

限制与约定

测试点编号	$\| S \| \leq$	特殊性质
$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 \leq T \leq 5$ ， $1 \leq | S | \leq 2^{20}$ 。

时间限制： $1 s$

空间限制： $512 MB$

下载

附加文件下载

Universal Online Judge

UOJ

#581. 【NOIP2020】字符串匹配

输入格式

输出格式

样例一

input

output

样例解释一

样例二

input

output

样例三

样例四

限制与约定

下载