#P4406. [Wc2016]论战捆竹竿

    ID: 3611 传统题 1000ms 256MiB 尝试: 63 已通过: 46 难度: 10 上传者: 标签>难度分类NOI/NOI+/CTS字符串KMPborder 链字符串周期图论状态扩展图动态规划单调队列优化 DP构造与建模复制数组处理环CF3000

[Wc2016]论战捆竹竿

[WC 2016] 论战捆竹竿

题目描述

有无限多根相同的短竹子,每根有 nn 节。从底端到顶端,各节的颜色由字符串 ss 表示,颜色用小写英文字母编号。

一开始只有一根短竹子。每次可以在现有竹竿的顶端再捆上一根短竹子:选一个 kk(0≤k≤n0\le k\le n),把新竹子底端的 kk 节与竹竿顶端的 kk 节按原顺序重合。一对重合的竹节必须颜色相同。新竹子未重合的部分从顶端伸出;不能把竹子倒过来。重合的两节在计算长度时只算一节。k=0k=0 表示首尾相接,k=nk=n 表示完全重合。

例如,若 ss 是 aba,捆上第二根后可能得到 abaaba、ababa 或 aba。若当前竹竿为 ababa,再次增加一根可得到 ababaaba、abababa 或 ababa。

求长度不超过 ww 的竹竿有多少种不同长度。若 w<nw<n,答案为 00。

输入格式

第一行一个整数 TT,表示数据组数。正式测试每份文件有 55 组,样例的组数以输入为准。

每组数据先输入两个正整数 n,wn,w;再输入一个长度为 nn 的小写字母串 ss,从底端到顶端描述一根短竹子的颜色。满足 1≤n≤5×1051\le n\le5\times10^5、1≤w≤10181\le w\le10^{18}。

输出格式

每组数据输出一行一个整数,表示可以捆出的不同长度数。

样例 #1

样例输入 #1

1
4 11
bbab

样例输出 #1

5

竹竿可能为 bbab、bbabbab、bbabbbab、bbabbabbab、bbabbabbbab、bbabbbabbab。最后两种均为 1111 节,故不同长度是 4,7,8,10,114,7,8,10,11。

样例 #2

样例输入 #2

2
44 1000
baaaaaabaabbaaabbbbabbbaaabbbababaaabaaabaaa
41 1000
abaabbabaaabaabbbbbbbbbbbababbbbaaabaabbb

样例输出 #2

195
24

样例 #3

样例输入 #3 · 样例输出 #3

提示

原赛测试点的附加条件如下:

测试点 nn ww 其它条件
1 ≤10\le10 只含 a 和 b
2 ≤20\le20 无
3–4 ≤100\le100 ≤1018\le10^{18}
5–6 ≤103\le10^3
7–10 ≤5×104\le5\times10^4 ≤105\le10^5
11–12 ≤7×104\le7\times10^4 ≤1018\le10^{18}
13–16 ≤105\le10^5
17–20 ≤5×105\le5\times10^5