比赛场次 511
比赛名称 近5年noip/csp题目回顾
比赛状态 已结束比赛成绩
开始时间 2022-06-25 08:30:00
结束时间 2022-06-26 17:30:00
开放分组 全部用户
注释介绍 只有历年比赛题才最接近比赛题。
题目名称 字符串匹配
输入输出 2020string.in/out
时间限制 1000 ms (1 s)
内存限制 512 MiB
测试点数 25 简单对比
用户 结果 时间 内存 得分

字符串匹配

★★★☆   输入文件:2020string.in   输出文件:2020string.out   简单对比
时间限制:1 s   内存限制:512 MiB

【题目描述】

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

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

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

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

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

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

【输入格式】

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

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

【输出格式】

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

【样例1输入】

3
nnrnnr
zzzaab
mmlmmlo

【样例1输出】

8
9
16

【样例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。

【样例2输入】

5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab

【样例2输出】

156
138
138
147
194

【测试样例】

water.zip

【数据规模与约定】

对于所有测试点,保证$1\leq T\leq 5,1\leq |S|\leq 2^{20}$。

【来源】

NOIP 2020 Task 2