如何使用前缀和优化解决AtCoder BCon 249 E题的RLE动态规划问题？

本文共计584个文字，预计阅读时间需要3分钟。

题目：AtCoder 动态规划，前缀和优化+传送门：E+RLE（atcoder.jp）内容：求满足原长度为N且转换后长度小于N的字符串组成的字符串的个数，输出时对P取模。其中，转换规则为，将连续相同的字符替换为该字符的数量。

AtCoder：动态规划，前缀和优化

传送门：E - RLE (atcoder.jp)

题意：

求满足原长为N且转换后长度严格小于N条件的小写字母组成的字符串的数量，输出时对P取模。

其中，转换规则为，将连续相同的字串替换为“字符数量+字符”，如aaa替换为3a。

思路：

• 状态表示：

  

  f_i,j：原长为i且转换后长度为j的字符串的数量。

• 状态转移：

　　初始化：将仅包含一种字符的所有字符串进行初始化。