首页 > 试题广场 >

遗忘的记忆

[编程题]遗忘的记忆

小苯是“小红书app”的一位博主，他在自己的账号中发布了 $n$ 篇分享，编号从 $1$ 到 $n$ 。

有一天他想试试看自己能不能准确的记住这 $n$ 篇分享的点赞数，但他很快就发现凭自己的记忆力根本没法准确地记住每一篇的点赞数。但他记得如下两种信息：

$\bullet$ 每篇分享的点赞量都为正数，且不超过 $m$ 。
$\bullet$ 第 $i$ 篇分享的点赞量和第 $i-1$ 篇分享的点赞量的大小关系。

他想知道，在已知这些信息的前提下，所有分享的点赞量有多少种不同的可能。

（结果可能很大，请输出其对 $1000000007$ 取模的值）

输入包含两行。
第一行两个正整数 ，分别表示分享的总个数和每篇分享的点赞数的上限。
第二行一个长度为  的字符串 ，其中只包含 ">"，"<"，"=" 这三种字符。如果   '>' ，则第  篇分享的点赞量严格高于第  篇，"<" 和 "=" 同理。

输入一行一个整数表示符合条件的分享点赞量个数，结果对  取模。

示例1

输入

4 3
<=>

[1, 2, 2, 1]
[2, 3, 3, 2]
[1, 3, 3, 1]
[2, 3, 3, 1]
[1, 3, 3, 2]
一共五种可能

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

动态规划前缀和小红书

难度：

0条回答 10收藏 432浏览

遗忘的记忆

扫一扫，把题目装进口袋