P3917 - 上升子序列

内存限制：128 MB 时间限制：2 S

题面：传统评测方式：文本比较上传者：

提交：2 通过：2

提交提交记录统计 Web Board

给定一个只包含整数的序列(序列元素的绝对值大小不超过10⁹),你需要计算上升子序列的个数,满足如下条件的称之为一个上升子序列:

如果两个上升子序列相同,那么只需要计算一次。例如:序列{1,2,3,3}有4个上升子序列,分别为{1,2}{1,3},{1,2,3},{2,3}

输入的第一行是一个整数n,表示序列长度。接下来一行是n个整数,表示序列。

输出仅包含一行,即原序列有多少个上升子序列。由于答案可能非常大,你只需要输出答案模10^9+7的余数。

4
1 2 3 3

对于 30% 的数据，N ≤ 5000
对于 100% 的数据，N ≤ 10⁵

TJOI2014

3917: 上升子序列