84 人解决,111 人已尝试。
95 份提交通过,共有 351 份提交。
3.8 EMB 奖励。
单点时限: 2.0 sec
内存限制: 512 MB
你最后还是决定饮茶放工,出去和队友吃火锅。不过在此之前火锅店老板已经对评论区进行了一次公关,你已经看不到多少中肯的评价了。同时,你也在评论区发现了一些端倪:因为老板请了水军,评论区的评论呈现出有一些有趣的特点。例如每一条评论的开头都离不开某几句话,因此你用一个小写字母 (a
- z
) 来表示一种评论。
你还发现评论都是用比较拙劣的自动化工具刷的,因为不仅只有几种评论,依次查看评论甚至发现了 循环节。根据你多年的脚本经验,这个脚本里面有一个长度为 $p$ 的评论列表,这个脚本会按顺序循环往复地发布这 $p$ 条评论。如果我们用字符串 $s = s_1 s_2\dots s_{|s|}$ 表示一系列连续的评论,那么我们说 $p$ 是 $s$ 的循环节,当且仅当:
你现在爬取了评论区所有的 $n$ 条评论,你很好奇老板刷评论的脚本里面的评论列表长什么样。不过,在老板操作以前可能已经存在一些评论了,你不知道老板是从哪一条评论开始用脚本刷评论的,因此你想知道每一个后缀的周期性。具体而言,对于 $i=1 \dots n$,假设最后的 $i$ 条评论是用脚本刷的,你需要求出脚本中所有可能循环节的大小(也即评论列表长度)之和 $a_i$ :
$$ a_i = \sum_{p \text{是} s_{n - i + 1\dots n} \text{的周期}} p .$$
输入包含多组数据。第一行包含一个整数 $T$,代表数据组数。
每组数据的第一行包含一个正整数 $n$ ($1 \le n \le 10^6$),代表评论区评论的数量;第二行包含一个仅包含小写字母的字符串 $s$。
保证所有数据的 $n$ 总和不超过 $10^6$。
对每组数据,在一行内输出 $n$ 个用空格分隔的整数 $a_1,\ a_2,\ \dots,\ a_n$。
3 5 ababa 14 nunhehhehahhhh 8 shanghai
1 2 5 6 11 1 3 6 10 5 11 7 15 24 10 21 12 13 14 1 2 3 4 5 6 7 8
对于第一组数据而言:
84 人解决,111 人已尝试。
95 份提交通过,共有 351 份提交。
3.8 EMB 奖励。
创建: 1 年,5 月前.
修改: 1 年,5 月前.
最后提交: 6 月前.
来源: N/A