1 条题解
-
0
题目分析
首先我们设 表示以 作为结尾的区间中总共有多少个 "bessie"。
考虑转移。
首先我们需要找到最近的一个 "bessie",我们可以考虑设一个 表示找到的上一个 "bessie" 的前 项的起始位置。
举个例子,字符串 "bessie" 就有 。
那这个怎么算呢?我们找到一个字符 "bessie" 的哪一位,设为 位,则它的开头显然是 。
接下来,我们把贡献分成两份,一份是上一个 "bessie" 的贡献,一份是其他 "bessie" 的贡献。
后者的贡献我们发现就是 ,因为往后的字符串与当前的这个 "bessie" 不可以同时出现。
对于当前的字符串,我们发现对于 而言都可以包含当前这个 "bessie",因此 "bessie" 总数会增加 。
得转移方程:
而问题问的是所有区间,所有我们需要把它们加起来,即:
- 1
信息
- ID
- 170
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者