真题模拟赛第四场|Ant|2023.04.04算法岗笔试
- Status
- Done
- Rule
- IOI
- Problem
- 3
- Start at
- 2023-4-14 19:00
- End at
- 2023-4-14 20:20
- Duration
- 1.3 hour(s)
- Host
- Partic.
- 81
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
小红是一名热爱字符串算法的程序员。他最近遇到了一个有趣的问题。
给定一个字符串 s,字符串中包含多少个 red
子串,就给这个字符串一个权值,权值就是 red
子串的数量。
例如:redd 权值为1,redredr 权值为2,reed 权值为0
现在考虑计算一个字符串 s 所有非空子序列的权值和。 答案可能很大,请对1e9+7取模
长为 n 的字符串的非空子序列为 2n−1 个。
输入第一行为一个字符串s(1≤∣s∣≤100000)。
输出字符串所有非空子字符串的权值和。
输入
rredd
输出
9
考虑枚举第i
个元素对结果的贡献,即第i
个元素可以构成多少个"red"
子序列,如果第i
个元素不是字符'e'
,那么对结果的贡献肯定为0
,如果是'e'
,则需要去统计i
左边有多少个字符'r'
以及右边有多少个字符'd'
,右边有多少个字符'd'
可以使用一个后缀数组g
预处理一下,对于左边的每一个字符'r'
,设它对应的下标为j
,0≤j≤n−1,它所能构成的非空子序列数量为2j
(即它左边有多少个字符,比如j=0
,它左边没有字符,就只有它自己一种选择,对应方案数为20=1)
这个地方,题目也给了提示: