题目内容

塔子哥是一名热爱字符串算法的程序员。他最近遇到了一个有趣的问题。

思路：前后缀分解+贡献法计数+乘法原理

考虑枚举第i个元素对结果的贡献，即第i个元素可以构成多少个"red"子序列，如果第i个元素不是字符'e'，那么对结果的贡献肯定为0，如果是'e'，则需要去统计i左边有多少个字符'r'以及右边有多少个字符'd'，右边有多少个字符'd'可以使用一个后缀数组g预处理一下，对于左边的每一个字符'r'，设它对应的下标为j，$0\le j \le n-1$，它所能构成的非空子序列数量为$2^j$

（即它左边有多少个字符，比如j=0，它左边没有字符，就只有它自己一种选择，对应方案数为$2^0=1$）

这个地方，题目也给了提示：