#P4406. [Wc2016]论战捆竹竿
[Wc2016]论战捆竹竿
[WC 2016] 论战捆竹竿
题目描述
有无限多根相同的短竹子,每根有 节。从底端到顶端,各节的颜色由字符串 表示,颜色用小写英文字母编号。
一开始只有一根短竹子。每次可以在现有竹竿的顶端再捆上一根短竹子:选一个 (),把新竹子底端的 节与竹竿顶端的 节按原顺序重合。一对重合的竹节必须颜色相同。新竹子未重合的部分从顶端伸出;不能把竹子倒过来。重合的两节在计算长度时只算一节。 表示首尾相接, 表示完全重合。
例如,若 是 aba,捆上第二根后可能得到 abaaba、ababa 或 aba。若当前竹竿为 ababa,再次增加一根可得到 ababaaba、abababa 或 ababa。
求长度不超过 的竹竿有多少种不同长度。若 ,答案为 。
输入格式
第一行一个整数 ,表示数据组数。正式测试每份文件有 组,样例的组数以输入为准。
每组数据先输入两个正整数 ;再输入一个长度为 的小写字母串 ,从底端到顶端描述一根短竹子的颜色。满足 、。
输出格式
每组数据输出一行一个整数,表示可以捆出的不同长度数。
样例 #1
样例输入 #1
1
4 11
bbab
样例输出 #1
5
竹竿可能为 bbab、bbabbab、bbabbbab、bbabbabbab、bbabbabbbab、bbabbbabbab。最后两种均为 节,故不同长度是 。
样例 #2
样例输入 #2
2
44 1000
baaaaaabaabbaaabbbbabbbaaabbbababaaabaaabaaa
41 1000
abaabbabaaabaabbbbbbbbbbbababbbbaaabaabbb
样例输出 #2
195
24
样例 #3
提示
原赛测试点的附加条件如下:
| 测试点 | 其它条件 | ||
|---|---|---|---|
| 1 | 只含 a 和 b |
||
| 2 | 无 | ||
| 3–4 | |||
| 5–6 | |||
| 7–10 | |||
| 11–12 | |||
| 13–16 | |||
| 17–20 | |||